Partition List

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->null and x = 3, return 1->2->2->4->3->5->null.

http://www.lintcode.com/en/problem/partition-list/

Discussion

刚开始忽略了保持相对顺序不变整成排序了。。。就是用两个dummy分别建立part 1 和part 2最后再连起来OK了。。

Solution

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode dummy(-1);
        dummy.next = head;
        ListNode dummy2(-1);
        dummy.next = head;
        ListNode *list1 = &dummy;
        ListNode *list2 = &dummy2;
        ListNode *cur = head;
        while(cur != NULL) {
            if(cur->val < x) {
                list1->next = cur;
                list1 = list1->next;
            } else {
                list2->next = cur;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        list1->next = dummy2.next;
        list2->next = NULL;//刚开始漏了这句，报错了，因为list2有可能没有指向队尾，这样的话就循环了。
        return dummy.next;
    }
};

上面程序中没有给dummy2.next=head。歪打正着了，不然会超时，dummy和dummy2都不用head作为next，因为while循环里有判断。

不用dummy更简单：

ListNode *partition(ListNode *head, int x) {
        ListNode *dummy_smaller = new ListNode(INT_MIN);
        ListNode *dummy_larger = new ListNode(INT_MIN);
        ListNode *smaller = dummy_smaller;
        ListNode *larger = dummy_larger;

        while (head) {
            if (head->val < x) {
                smaller->next = head;
                smaller = smaller->next;
            } else {
                larger->next = head;
                larger = larger->next;
            }
            head = head->next;
        }
        smaller->next = dummy_larger->next;
        larger->next = nullptr;

        return dummy_smaller->next;
    }