分割链表
1.问题
给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。你不需要 保留 每个分区中各节点的初始相对位置
2.代码实现
//5.分割链表
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListnode
{SLTDataType val;struct SListnode* next;
}ListNode;ListNode* createNode(SLTDataType val)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = val;newnode->next = NULL;return newnode;
}struct ListNode* partition(struct ListNode* head, int x)
{ListNode* pcur = head;ListNode* Lhead = (ListNode*)malloc(sizeof(ListNode));ListNode* Hhead = (ListNode*)malloc(sizeof(ListNode));ListNode* L1 = Lhead;ListNode* L2 = Hhead;while (pcur){if (pcur->val < x){L1->next = pcur;//L1相当于Lhead的末尾结点指针（初始状态都是链表的头），每进循环一次，往前走一步L1 = L1->next;}else{L2->next = pcur;//L2相当于Hhead的末尾结点指针（初始状态都是链表的头），每进循环一次，往前走一步L2 = L2->next;}pcur = pcur->next;}L2->next = NULL;//修改Hhead链表 末尾节点指向的指针进行初始化，如果没有这个，代码可能就会出现死循环 因为不确定head最后一个节点是否为Hhead链表的最后一个节点，为了保险起见 就使L2->next = NULLL1->next = Hhead->next;return Lhead->next;
}int main()
{ListNode* node1, * node2, * node3, * node4, * node5, * node6;node1 = createNode(1);node2 = node1->next = createNode(4);node3 = node2->next = createNode(3);node4 = node3->next = createNode(2);node5 = node4->next = createNode(5);node6 = node5->next = createNode(5);//创建一个链表ListNode* newhead = partition(node1, 3);while (newhead){printf("%d ", newhead->val);newhead = newhead->next;}return 0;
}