您现在的位置是：首页 >学无止境 >【数据结构】--单链表力扣面试题⑤链表分割网站首页学无止境

目录

一、有相对顺序的链表分割

二、无相对顺序的链表分割

一、有相对顺序的链表分割

题述：现有一链表的头指针ListNode* phead,给一定值x,编写一段代码将所有<x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排序后的链表的头指针。

示例如下：

思路：难就难在不能改变相对顺序。那我们的思路是创建两个链表，一个链表尾插<x的值，一个链表尾插>x的值，然后再把两个链表顺序链接即可。并且我们还会给两个链表定义尾指针，lessTail和greaterTail，并且会开辟一个头结点，这两个操作都是为了方便尾插。没有头结点还要多加一个判断。

但是如果开辟头结点，还要多两个操作：

1、我们题中默认都是没有头结点的，如果要返回头指针，他一定是要返回头结点的下一节点的地址，并且在两个链表链接过程中，一定是链接后面的头结点后的那一个节点。

2、要释放节点的内存，要返还给操作系统。

小知识：一般上oj上是不会限制空间复杂度的，如果出现报错，内存限制：您的程序使用了超出限制的内存。这种问题可能是由死循环等的问题造成的。

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{
	struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
	lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟一个头结点,使头指针和尾指针都指向头结点，以便遍历链表
	greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* cur = phead;//用cur来遍历原链表
	while (cur)//结束条件一定是遍历完原链表
	{
		if (cur->val < x)
		{
			lessTail->next = cur;
			lessTail = cur;
		}
		else
		{
			greaterTail->next = cur;
			greaterTail = cur;
		}
		cur = cur->next;//无论如何,链接完一个结点后都要往下走一次
	}
	lessTail->next = greaterHead->next;//将>=x的链表链接在<x的链表后面。
	//这里是=greaterHead->next的原因是greaterHead是头结点，是你自己开辟的，题里面不要这个！
	greaterTail->next = NULL;//使>=x的链表最后指向是NULL,防止构成环形链表
	struct ListNode* newnode = lessHead->next;//因为lessHead是头结点，我们不要！
	free(lessHead);//因为lessHead始终指向头结点，所以直接释放
	free(greaterHead);
	return newnode;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	int k = 5;
	n1->val = 1;
	n2->val = 2;
	n3->val = 4;
	n4->val = 3;
	n5->val = 9;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	struct ListNode* obj = partition(n1, k);
	while (obj)
	{
		printf("%d", obj->val);
		obj = obj->next;
	}

	return 0;
}

运行代码如下：

如果不要求相对顺序呢？

二、无相对顺序的链表分割

示例： 

 思路：给一个头head和一个尾tail,<x值的头插，>=x值的尾插即可实现。毕竟不要求相对顺序。只要求<x的节点在前面，>=x的节点在后面即可。

并且既要头插又要尾插的话就不建议创建一个头结点了，因为夹在中间，他还没用，会造成妨碍。

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{
	struct ListNode* head = NULL, * tail = NULL;
	struct ListNode* cur = phead,* prev = NULL;
	while (cur)
	{
		if (cur->val < x)
		{//头插要判断，如果是在中间头插，先要保存cur的下一个节点的地址才行
			if (head == NULL)
			{
				head = tail = cur;
				cur = cur->next;
			}
			else
			{
				prev = cur->next;
				cur->next = head;
				head = cur;
				cur = prev;
			}
		}
		else
		{//尾插就不需要考虑太多了
			if (head == NULL)
			{
				head = tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = cur;
			}
			cur = cur->next;
		}
	}
	return head;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	int k = 5;
	n1->val = 1;
	n2->val = 2;
	n3->val = 4;
	n4->val = 3;
	n5->val = 9;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	struct ListNode* obj = partition(n1, k);
	while (obj)
	{
		printf("%d", obj->val);
		obj = obj->next;
	}

	return 0;
}