【算法】将单向链表按某值划分成左边小、中间相等、右边大的形式
【算法】将单向链表按某值划分成左边小、中间相等、右边大的形式
题目
给定一个单向链表的头节点head，节点的值类型是型，再给定一个整数pivot。实现一个调整链表的函数，
将表调整为左部分都是值小于 pivot 的节点，
中间部分都是值等于pivot的节点，
右部分都是值大于 pivot的节点。
除这个要求外，对调整后的节点顺序没有更多的要求。
例如:链表9->0->4->5->1，pivot=3。
调整后链表可以是1->0->4->9->5，
也可以是0->1->9->5->4。
总之，满足左部分都是小于3的节点，中间部分都是等于3的节点(本例中这个部 分为空)，右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
进阶题
在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，
要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。
例如:链表9->0->4->5->1，pivot=3。
调整后的链表是0->1->9->4->5。
在满足原问题要求的同时，左部分节点从左到 右为0、1。
在原链表中也 是先出现0，后出现1;
中间部分在本例中为空，不再 讨论;
右部分节点 从左到右为9、4、5。
在原链表中也是先出现9，然后出现4， 最后出现5。
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
链表结构如下：
public static class Node {
public Node next;
public int value;
public Node(int data) {
value = data;
}
}基础解法
思路
1、按链表顺序，用数组装每一个节点
2、用荷兰国旗算法对数组排序，其实就是快拍的partition过程，详文见https://cloud.tencent.com/developer/article/1606352
3、将数组还原为链表
代码实现
public static Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
cur = head;
// 把链表的值复制到数组中
for(i = 0; i < nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
// 对数据进行“荷兰国旗”分组
arrPartition(nodeArr, pivot);
// 重新把链表连接
for(i = 1; i < nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
/// 荷兰国旗算法
public static void arrPartition(Node[] nodeArr, int pivot) {
int more = nodeArr.length;
int less = -1;
int i = 0;
while(i != more) {
if (nodeArr[i].value < pivot) {
less++;
swap(nodeArr, less, i);
i++;
}else if(nodeArr[i].value > pivot) {
more--;
swap(nodeArr, i, more);
}else {
i++;
}
}
}进阶解法
思路
1、使用6个指针建立小于，等于，大于pivot的链表区域
2、每一次遍历都更新对应区域的头尾节点
3、全部遍历节点完毕后，将连接小于的尾->等于的头->等于的尾->大于的头
代码实现
public static Node listPartition2(Node head, int pivot) {
// 小于pivot的链表头尾节点
Node lessSt = null;
Node lessEnd = null;
// 等于pivot的链表头尾节点
Node eqSt = null;
Node eqEnd = null;
// 大于pivot的链表头尾节点
Node moreSt = null;
Node moreEnd = null;
// 用于保存next指针
Node next = null;
// 遍历链表
while(head != null) {
next = head.next;
// 为了不污染小于，等于，大于的指针next，这里清空
head.next = null;
if(head.value < pivot) {
if(lessSt == null) {
lessSt = head;
lessEnd = head;
}else {
lessEnd.next = head;
lessEnd = head;
}
}else if(head.value == pivot) {
if(eqSt == null) {
eqSt = head;
eqEnd = head;
}else {
eqEnd.next = head;
eqEnd = head;
}
}else {
if(moreSt == null) {
moreSt = head;
moreEnd = head;
}else {
moreEnd.next = head;
moreEnd = head;
}
}
head = next;
}
// 小于和等于区域相连
if(lessEnd != null) {
lessEnd.next = eqSt;
// 判断equal的结尾指针是否为空
eqEnd = eqEnd == null ? lessEnd : eqEnd;
}
// 最后等于，大于区域相连
if (eqEnd != null) {
eqEnd.next = moreSt;
}
if (lessSt != null) {
return lessSt;
}
if (eqSt != null) {
return eqSt;
}
if (moreSt != null) {
return moreSt;
}
return null;
}腾讯云开发者
