c语言-数据结构-链表分割

链表分割实际上是给定一个值，遍历链表把链表中小于该值的节点与大于该值的节点分开，一般是将小于该值的节点放到链表的前面部分，大于该值的节点放在链表的后面部分。

链表分割示意图如下：

思路：首先创建两条带哨兵位节点的新链表并且用big、small指针维护，比8大的节点放在big链表，比8小的节点放在small链表。

两条新链表则需要创建两个哨兵位。哨兵位节点的作用顾名思义，仅仅是起到一个“站岗”的作用，也就是把要插入到新链表中的节点直接插到哨兵位节点的后面。

情况一：

遍历链表，发现比8大的节点将其放到big哨兵位节点的后面，如下图:

注意：这里不能直接让small和big指针进行遍历，因为如果这两个指针往后移动则找不到哨兵位节点的位置了，也就找不到链表的初始位置，还会面临内存泄漏的风险（因为哨兵位是malloc来的，没有哨兵位的位置就无法对其进行释放）。因此再定义两指针b_travel和s_travel代替移动，并且将cur指针移动至下一个节点。

情况二：

若发现比8小的节点将其放到small哨兵位节点的后面，如下图：

同理将cur指针至下一个节点，每次拿下来一个节点都要更新b_travel和s_travel指针指向的位置。如此重复以上操作，直到cur指针指向NULL说明链表已遍历结束。

合并链表：

接下来是最关键的一步，就是将small链表和big链表合二为一，最后返回small哨兵位的下一个节点的地址，即合并后链表的头节点地址。

切记最后返回的是small哨兵位节点的下一个节点的地址，因为small和big开辟的哨兵位节点只是用于“站岗”，最后链表链接完成后需要将这两个哨兵位释放。

铺垫了那么久接下来就是代码实现（测试代码包括链表的创建、打印以及链表分割功能）：

#include<stdio.h>
#include<stdlib.h>typedef struct ListNode //创建节点结构体
{int data;//存放数据struct ListNode* next;//指向下一个节点
}ListNode;//链表分割函数
ListNode* partition(ListNode* head, int x) {struct ListNode* small = NULL;//开始先创建4个指针，两两维护链表struct ListNode* big = NULL;struct ListNode* s_travel = NULL;//这两个指针用于遍历链表struct ListNode* b_travel = NULL;//开辟两个哨兵位节点s_travel = small = (struct ListNode*)malloc(sizeof(struct ListNode));b_travel = big = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = head;//用cur指针代替head遍历链表while (cur)//cur为空跳出循环{if (cur->data < x)//小于x的节点放到small链表中{s_travel->next = cur;s_travel = s_travel->next;}else//大于x的节点放到big链表中{b_travel->next = cur;b_travel = b_travel->next;}cur = cur->next;//cur往后走}b_travel->next = NULL;//合并链表s_travel->next = big->next;struct ListNode* poi = small;//记住small哨兵位节点的位置small = small->next;//small指向哨兵位后一个节点，也就是链表的头节点free(big);//释放哨兵位free(poi);return small;//返回链表头节点位置
}//打印链表函数
void Print(ListNode* phead)
{ListNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL");//模拟链表最后指向的是NULL
}int main()
{ListNode* n1 = (ListNode*)malloc(sizeof(ListNode));//创建5个节点，为了测试分割链表函数ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));ListNode* n5 = (ListNode*)malloc(sizeof(ListNode));ListNode* plist = n1;//指向头节点的头指针plistn1->data = 12;//给每个节点都赋值n2->data = 6;n3->data = 23;n4->data = 18;n5->data = 2;n1->next = n2;//手动构建链表n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;Print(plist);//打印分割之前的链表ListNode* newhead = partition(plist, 8);//分割后返回新的头节点printf("\n分割后:");Print(newhead);//打印分割之后的链表return 0;
}

运行结果：