【Leetcode】【Medium】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.

解题思路：

1、先条件：输入链表不为空；

2、表头可能改变，因此需要新建一个结点指向表头，或使用二维指针；

3、不变参数：

　　curNode永远指向待操作结点的前驱（方便删减）

　　small_end永远指向已经分割的所有小结点中，最后一个结点

　　big_begin永远指向已经分割的所有大结点中，第一个结点

　　small_end->next = big_begin;

4、curNode->next为NULL时，循环结束。当发现小结点时，插入small_end和big_begin中间；

代码：

/**
 * 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) {
        if (head == NULL)
            return head;
        ListNode* prehead = new ListNode(0);
        prehead->next = head;
        ListNode* curNode = prehead;
        ListNode* small_end = NULL;
        ListNode* big_begin = NULL;
        
        while (curNode->next && curNode->next->val < x)
            curNode = curNode->next;
        
        small_end = curNode;
        big_begin = small_end->next;
        
        while (curNode->next) {
            if (curNode->next->val < x) {
                small_end->next = curNode->next;
                small_end = small_end->next;
                curNode->next = curNode->next->next;
                small_end->next = big_begin;
            } else {
                curNode = curNode->next;
            }
        }
        
        head = prehead->next;
        delete prehead;
        return head;
    }
};