链表分割（C语言）

链表分割（C语言）

【题目描述】
给你一个链表的头节点 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]

题目来源（力扣）：分割链表

【基本思路】
遍历一次原链表，将 所有小于 x 的节点 与 所有大于或等于 x 的节点 分别组成为两个链表，最后让（小于 x 的节点组成的）链表与（大于或等于 x 的节点组成的）链表拼接构成新链表，然后再处理一下细节即可。

注：这两个链表都带有哨兵位（可以使代码更简洁）。

【代码实现】

typedef struct ListNode ListNode;

struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)  // 如果传入的链表是空链表
        return NULL;

    ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));  // 哨兵位
    ListNode* lessTail = lessHead;
    lessTail->next = NULL;
    ListNode* greaterHead = (ListNode*)malloc(sizeof(ListNode));  // 哨兵位
    ListNode* greaterTail = greaterHead;
    greaterTail->next = NULL;

    ListNode* cur = head;
    while(cur)
    {
        if(cur->val < x)  // 找小于x的节点
        {
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        else  // 找大于或等于x的节点
        {
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
        }

        cur = cur->next;
    }

    lessTail->next = greaterHead->next;  // 对两个链表进行拼接
    greaterTail->next = NULL;  // 置空，防止新链表出现环
    ListNode* list = lessHead->next;  // list是新链表真正意义上的头节点
    free(greaterHead);  // 释放哨兵位
    free(lessHead);  // 释放哨兵位

    return list; 
}

【类似题目】
合并两个有序链表

本专栏
有关链表的题目

其它专栏
有关数组的题目