将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点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)。
解题思路:
原问题的思路
(1)使用一个辅助数组来存放链表,然后将数组进行“荷兰国旗问题”那样的划分出小于区、大于区和等于区。(不懂的可以去看我那篇荷兰国旗问题的博客,里面有详细解释)
(2)划分好之后,将数组中的值依次拷贝到链表中,就大功告成。
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
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 small = -1;
int big = nodeArr.length;
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
进阶问题的思路
因为要求在左、中、右三个部分的内部也做顺序要求,所以我们需要稳定的算法。
想象有三个单独的链表,small、equal和big。相当于小于、等于、大于区,每个链表设置一个头节点和尾节点。
(1)先遍历一遍链表,分别找到第一个小于、等于、大于pivot的节点,将头节点和尾节点同时设置为找到的对应节点。
(2)继续遍历,找到符合要求的节点就把它连到尾节点的下一个节点,因为一开始头节点和尾节点是同一个节点,所以这个操作相当于将下一个节点和头节点连起来了。同时,将尾节点设置为加进来的新节点。
(3)遍历完成之后,把3个链表串起来。具体操作就是将small链表的尾节点的下一个节点指向equal链表的头节点,equal链表的尾节点的下一个节点指向big链表的头节点。
public static Node listPartition2(Node head, int pivot) {
Node sHead = null; // small head
Node sTail = null; // small tail
Node eHead = null; // equal head
Node eTail = null; // equal tail
Node bHead = null; // big head
Node bTail = null; // big tail
Node next; // save next node
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sHead == null) {
sHead = head;
sTail = head;
} else {
sTail.next = head;
sTail = head;
}
} else if (head.value == pivot) {
if (eHead == null) {
eHead = head;
eTail = head;
} else {
eTail.next = head;
eTail = head;
}
} else {
if (bHead == null) {
bHead = head;
bTail = head;
} else {
bTail.next = head;
bTail = head;
}
}
head = next;
}
// small and equal reconnect
if (sTail != null) {
sTail.next = eHead;
eTail = eTail == null ? sTail : eTail;
}
// all reconnect
if (eTail != null) {
eTail.next = bHead;
}
return sHead != null ? sHead : eHead != null ? eHead : bHead;
}