题目链接
题目描述:给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
实例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
题解:
乍一看本题和快速排序的切分过程有些类似,但快速排序一般应用于数组中,而本题的数据结构为单链表,显然在交换元素部分有明显的区别。不过,双指针的思路可以借鉴。接下来让我们用双指针解决此题。
解决链表题可以使用建立虚拟头结点的技巧,同时要注意处理野指针。
- 引入双指针before,after分别用于存储小于x和大于等于x两个链表
- 两链表设置虚拟头结点可以减少条件判断(自行举例)
- 用head遍历原有链表
- 当值小于x,将该结点接入before链表中
- 当值大于等于x,将该结点接入after链表中
- head为空跳出循环
- 现在将after链接到before后
- 要注意处理掉虚拟头结点,也就是before和after在链接和返回是向后移一位即可达到处理虚拟头结点的效果
注意,要体会这个过程中,我们没有使用任何额外的空间,只是将原有链表结点进行移动。对于after->next = NULL;
,很多盆友可能有疑问,单单知晓这一步是处理野指针显然不能满足大家的求知欲。而通常解释这一步是为了避免形成环形链表。不过,这个解释也有一点点抽象,所以,解决这个问题最好的办法就是打断点自己过一遍程序,一切都明白了。
当然,因为是题解,我会给出一个例子的手绘示意图,可能会让你更直观的理解为什么要消除环形?还是如上文所说,要么亲力亲为,要么理解那句话。。。
算法
cpp
1 | class Solution { |
若还有疑问可以去英文版leetcode的discuss区看大神们的解答!