086 - Partition List

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

Hide Tags

Linked List Two Pointers

 

用两个虚拟的头，依次分别收集小于x的以及大于等于x的，最后连起来即可。

要注意的是，每处理完一个node，都要把它原来的next指针清空，不然最后可能会弄成一个环。

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode small(0);
        ListNode large(x);
        ListNode* ss = &small;
        ListNode* ll = &large;
        while(head)
        {
            if(x>head->val)
            {
                ss->next = head;
                ss = ss->next;
            }
            else
            {
                ll->next = head;
                ll = ll->next;
            }
            ListNode* temp = head->next;
            head->next = NULL;
            head = temp;
        }
        ss->next = large.next;
        return small.next;
    }
};

8 ms.