题目链接：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.

这道题的要求是将链表中小于x的节点放到左侧，大于等于x的节点放到右侧，要保持原有的相对顺序。

思路比较简单，用l标识左侧小于x的节点的最后位置，则每次右移r，当r指向的节点小于x时，把其放到l后面即可。

时间复杂度：O(n)

空间复杂度：O(1)

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
34

class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        ListNode *h = new ListNode(0);
        h -> next = head;
        
        ListNode *l = h, *r = h;
        while(r -> next != NULL)
        {
            if(r -> next -> val < x)
            {
                if(l != r)
                {
                    ListNode *tempr = r -> next -> next;
                    r -> next -> next = l -> next;
                    l -> next = r -> next;
                    l = r -> next;
                    r -> next = tempr;
                }
                else
                {
                    l = l -> next;
                    r = r -> next;
                }
            }
            else
                r = r -> next;
        }
        
        return h -> next;
    }
};