【LeetCode】86. 分隔链表

【题目描述】

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list

【解题思路】

1、首先找到分割节点的位置pos、以及其上一个节点pre_pos；

2、从分割节点pos的下个节点开始，遍历链表，把符合条件的节点插入到分割节点pos之前；

注：需要注意pre_pos要随着插入节点后而改变；

【提交代码】

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 
 9 
10 struct ListNode* partition(struct ListNode* head, int x){
11     struct ListNode *dummy;
12     struct ListNode *pos;
13     struct ListNode *pos_pre;
14     struct ListNode *pre;
15     struct ListNode *cur;
16 
17     dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
18     dummy->next = head;
19 
20     pos_pre = dummy;
21     // 找到分割位置，pos_pre指向分割节点的前一个节点
22     while( pos_pre->next != NULL )
23     {
24         if( pos_pre->next->val >= x )
25             break;
26 
27         pos_pre = pos_pre->next;
28     }
29 
30     pos = pos_pre->next;    // pos指向分割位置节点
31 
32     if( pos == NULL )
33         return head;
34 
35     pre = pos;
36     cur = pos->next;    // 分割位置的下一个节点
37     while( cur != NULL )
38     {
39         if( cur->val < x ) // 把符合条件的节点插入到分割位置之前
40         {
41             pre->next = cur->next;
42 
43             cur->next = pos;
44             pos_pre->next = cur;
45             pos_pre = cur;
46 
47             cur = pre->next;
48         }
49         else
50         {
51             cur = cur->next;
52             pre = pre->next;
53         }
54     }
55 
56     return dummy->next;
57 }