链表分割-双哨兵位

题目

现有一链表的头指针struct ListNode* pHead，给一定值x，编写一段代码将所有小于x的节点排在其余节点之前，且不能改变原来数据顺序，返回重新排列后的链表的头指针

示例：
pHead [1,5,2,7,3,4], x=5
输出 [1,2,3,4,5,7]

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* partition(struct ListNode* pHead, int x) {}

分析

思路：
创建两个新链表，分别存储小于x的节点和大于等于x的节点。将两个新链表链接起来成为新链表，返回新链表。
流程：
注：（great->g; less->l）
创建两个哨兵位，用gGuard和lGuard指向。创建gTail和lTail指向大小链表尾。
创建cur指针遍历原链表，当cur->val<x时尾插到lTail->next；否则尾插到gTail->next。
最后pHead指针存储新链表头，链接大小链表（lTail->next = gGuard->next;），再将新链表结尾指向NULL（gTail->next = NULL;）。
释放哨兵位。
返回pHead。

代码

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* partition(struct ListNode* pHead, int x) {
    struct ListNode* gGuard, * gTail, * lGuard, * lTail;
    gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位
    lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位
    gTail->next = lTail->next = NULL;

    struct ListNode* cur = pHead;
    while (cur)
    {
        if (cur->val < x)
        {
            lTail->next = cur;
            lTail = lTail->next;
        }
        else
        {
            gTail->next = cur;
            gTail = gTail->next;
        }
        cur = cur->next;
    }
    gTail->next = NULL;
    lTail->next = gGuard->next;
    pHead = lGuard->next;
    free(gGuard);
    free(lGuard);
    return pHead;
}

本题若使用不带头单链表，会遇到很为NULL的情况，使用哨兵位可以避免这个问题。