86.|86. 分隔链表
双指针法：
直觉
我们可以用两个指针pbig 和 psmall 来追踪上述的两个链表。两个指针可以用于分别创建两个链表，然后将这两个链表连接即可获得所需的链表。
算法
利用cur指针遍历原链表。若cur 指针指向的元素值 小于 x，该节点应当是 psmall 链表的一部分。因此我们将其移到 psmall 中。否则，该节点应当是pbig 链表的一部分。因此我们将其移到 pbig 中。
【86.|86. 分隔链表】遍历完原有链表的全部元素之后，我们得到了两个链表 psmall 和 pbig。原有链表的元素或者在psmall 中或者在 pbig 中，这取决于它们的值。
现在，可以将 psmall 和 pbig 连接，组成所求的链表。
为了算法实现更容易，我们使用了哑结点初始化。不能让哑结点成为返回链表中的一部分，因此在组合两个链表时需要向前移动一个节点。
注意:pbig->next需要置空。
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*struct ListNode *next;
* };
*/struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* cur = head;
struct ListNode bigdummy;
struct ListNode smalldummy;
bigdummy.next = head;
smalldummy.next = head;
struct ListNode *psmall, *pbig;
psmall = &smalldummy;
pbig = &bigdummy;
if(head == NULL || head->next == NULL)
return head;
while(cur != NULL){
if(cur->val < x){
psmall->next = cur;
psmall = psmall->next;
}else{
pbig->next = cur;
pbig = pbig->next;
}cur = cur->next;
}pbig->next = NULL;
psmall->next = bigdummy.next;
return smalldummy.next;
}推荐阅读
- leetcode|leetcode 92. 反转链表 II
- LeetCode|LeetCode 876. 链表的中间结点
- redis|redis 链表
- C语言数据结构之二叉链表创建二叉树
- 链表|链表 LC.19/83/92/61/143/21/160/141/147/138/142
- 数据结构|C++技巧（用class类实现链表）
- 27|27 二叉搜索树与双向链表
- LinkedBlockingQueue分析
- [Leetcode]24.|[Leetcode]24. 两两交换链表中的节点
- Golang使用快慢指针找不知长度链表的中间节点