题目

现有一链表的头指针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的情况，使用哨兵位可以避免这个问题。