86.Partition List

Tags: Medium Link List

Link: https://leetcode.com/problems/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.

---

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

---

Answer:

/**
 * 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 *dummy = new ListNode(0), *pre, *cur;
        dummy -> next = head;
        pre = dummy;

        while(pre -> next && pre -> next -> val < x) pre = pre -> next;
        cur = pre;

        while(cur -> next)
        {
            if(cur -> next -> val < x)
            {
                ListNode *tmp = cur -> next;
                cur -> next = tmp -> next;
                tmp -> next = pre -> next;
                pre -> next = tmp;
                pre = pre -> next;
            }
            else{
                cur = cur -> next;
            }  
        }

        return dummy -> next;
    }
};

解析：

类似于头插法，首先找到第一个不小于x的数，让pre为此结点的直接前驱，此种方法链表的变化顺序为：

1 -> 4 -> 3 -> 2 -> 5 -> 2 

1 -> 2 -> 4 -> 3 -> 5 -> 2 

1 -> 2 -> 2 -> 4 -> 3 -> 5

/**
 * 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 *dummy = new ListNode(-1);
        ListNode *newdummy = new ListNode(-1);
        ListNode *cur, *p;
        dummy -> next = head;
        cur = dummy;
        p = newdummy;

        while(cur -> next)
        {
            if(cur -> next -> val < x)
            {
                p -> next = cur -> next;
                p = p -> next;
                cur -> next = cur -> next -> next;
                p -> next = NULL;
            }
            else{
                cur = cur -> next;
            }
        }
        p -> next = dummy -> next;

        return newdummy -> next;
    }
};

解析：

将所有小于给定值的节点取出组成一个新的链表，此时原链表中剩余的节点的值都大于或等于给定值，只要将原链表直接接在新链表后即可(注意25、26行代码不可以交换顺序)，此种解法链表变化顺序为：

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2 
New:

Original: 4 -> 3 -> 2 -> 5 -> 2 
New:　  1

Original: 4 -> 3 -> 5 -> 2 
New:　  1 -> 2

Original: 4 -> 3 -> 5 
New:　  1 -> 2 -> 2

Original: 
New:　  1 -> 2 -> 2 -> 4 -> 3 -> 5