分割链表（面试题）

分割链表（面试题）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

思路：定义出两个头节点（s1，s2），把值小于x的节点尾插在s1之后，把等于或者大于x的节点尾插在s2之后，最后再把两个链表拼接。

图示：

 

 代码：

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode s1;
    struct ListNode s2;
    struct ListNode* cur1=&s1;
    struct ListNode* cur2=&s2;
    while(head){
        if(head->valnext=head;
            cur1=cur1->next;
        }else{
            cur2->next=head;
            cur2=cur2->next;
        }
        head=head->next;
    }
    cur2->next=NULL;
    cur1->next=s2.next;
    return s1.next;
}

这段代码难度并不大，但是要注意：定义头节点的时候并没有进行初始化，在最后链接两个单独的链表时，一定要先执行 cur2->next=NULL，在执行cur1->next=s2.next;因为当S2后没有进行尾插时，S2.next并不是空，此时直接链接可能出现错误，例如给定：head = [1,1], x = 1