【分割链表】

前言

大家好，今天我们来了解一下leetcode中比较简单的单链表问题。

一、题目描述

题目描述如下： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
使得所有 小于 x 的节点都出现在 大于或等于 x
的节点之前。

注意：你不需要 保留 每个分区中各节点的初始相对位置。

点击跳转：分割链表

---

二、算法思想

（一）值交换

1、题目解析

本题要求我们将链表中的数值进行重构，大于x的值都在小于x的值之前。
我们之前学习数组的时候使用过双指针的解法，一个front指针从前往后遍历，找到一个大于x的值就停下来，之后让back指针从后往前遍历，遇到小于x的值就和front中的值进行交换，之后front指针继续遍历，直到两指针相遇为止。
这里题目没有限制不可以开辟额外空间，那么我们就可以将链表中的数据放到数组中，交换结束后在拷贝回链表中。
此时的时间复杂度为O(n)，空间复杂度为O(n)。

动画演示如下：

双指针-- 数组

虽然借用数组来进行交换非常方便，
但是由于开辟数组这种方法空间复杂度较高，在很多情况下会受到限制，所以
这里我们不使用这种方法，不过可以使用双指针的思想：
设置两个指针，一个指针从头开始遍历，找到了数据大于x的节点后就让另一个节点从此处开始遍历，找到一个数据小于x的节点，之后交换两节点的数据。

动画演示如下：

双指针--链表

2、代码实现

代码如下：

typedef struct ListNode LN;

LN* partition(LN* head, int x) {
    if(!head || !head->next)
    {
        return head;
    }

   LN*less=head;
   LN*grea=head;
   while(less)
   {
       if(less->val>=x)
       {
           grea=less->next;
           while(grea)
           {
               if(grea->val<x)
               {
                   int tmp=grea->val;
                   grea->val=less->val;
                   less->val=tmp;
                   break;
               }
               grea=grea->next;
           }
       }
       if(!grea)
       break;
           less=less->next;
   }
   return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

运行实例：

时间复杂度O(n)，空间复杂度O(1)，时间复杂度虽然看起来是O(n)，但如果遇到前面都是大于x的数，后面都是小于x的数，
那么指针grea就需要遍历n/2次，时间复杂度近似与O(n^2)了已经，复杂度也很高的。

---

（二）重构链表

1、题目解析

上面我们交换的是节点中的数据，可是一个节点里不仅有数据域还有指针域，
那么我们能否通过改变指针的指向来改变链表呢？
下面让我们来尝试一下：
1.我们可以直接在原链表中进行更改；
2.创建一个新的链表，记录下小于x的最后一个节点和大于x的最后一个节点，之后分别进行尾插；
3.我们也可以创建两个新的链表，小于x节点连到一起，大于x的节点连到一起，
之后再将两个链表进行连接就可以了。（我们使用这种）

动画演示如下：

重构链表

2、代码实现

示例：

typedef struct ListNode LN;

LN* partition(LN* pHead, int x) {
	if (!pHead)
		return pHead;

	LN* lessHead = (LN*)malloc(sizeof(LN)); // 小于x的新链表
	lessHead->next = NULL;
	LN* greaHead = (LN*)malloc(sizeof(LN)); // 大于等于x的新链表
	greaHead->next = NULL;

	LN* pless = lessHead;
	LN* pgrea = greaHead;
	LN* cur = pHead;

	while (cur)
	{
		if (cur->val < x)
		{
			pless->next = cur;
			pless = pless->next;
		}
		else
		{
			pgrea->next = cur;
			pgrea = pgrea->next;
		}

		cur = cur->next;
	}

	pgrea->next = NULL; // 最后一个节点的next置空
	pless->next = greaHead->next; // 链接
	pHead = lessHead->next;

	free(lessHead);
	free(greaHead);

	return pHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

运行实例：

此方法的时间复杂度为O(n)，空间复杂度为O(1)，并且不论是哪一种情况都只会遍历一次。
视频中只演示了既存在大于x的值也存在小于x的值的情况，
这里我们还需要注意：
所有值都大于x，和所以值都小于x这两种特殊情况，如果感兴趣的话大家之后可以自行画图测试。

---

总结

以上就是今天分割链表题目的全部内容，题目不难，也不难讲。
不过如果总结一下我们会发现：
这简简单单的一道题我们一共就说了5种方法，而且我想大家肯定也会有自己的一些特殊的想法的，所以
我们不能仅限于解决问题，一个简单的题目我们可以通过各种各样的方法来解决，
我们还需要考虑使用什么方法可以使问题解决更加优雅、更加高效。
如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。