Leetcode and Lintcode

Partition List

Problem:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Leetcode link
Lintcode link

Solution:

It is an easy problem.
Just store the partition the linkedlist into to sub-linked list.
Finally, join them together.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*************************************************************************
	> File Name: PartitionList.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Mon 16 Nov 16:55:48 2015
 ************************************************************************/

public class PartitionList{
    public ListNode partition(ListNode head, int x) {
        ListNode current = head;
        ListNode leftDummy = new ListNode(-1);
        ListNode leftEnd = leftDummy;
        ListNode rightDummy = new ListNode(-1);
        ListNode rightEnd = rightDummy;
        
        while (current != null){
            if (current.val < x){
                leftEnd.next = current;
                leftEnd = leftEnd.next;
            } else {
                rightEnd.next = current;
                rightEnd = rightEnd.next;
            }
            current = current.next;
        }

        leftEnd.next = rightDummy.next;
        rightEnd.next = null;
        
        return leftDummy.next;
    }
    }
}