将单链表按值划分成左小中间等右边大的形式
程序员文章站
2022-05-06 11:33:07
...
题目:
给定一个单项链表的头结点dead,节点的值类型都是整型,在给定一个数pivot。实现一个调整链表的函数,将链表调整成左部分值都是小于pivot,中间部分都是等于值pivot,右边部分都是大于值pivot的部分。
等同于荷兰国旗问题
public static Node partition1(Node head, int num) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, num);
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
private static void arrPartition(Node[] nodeArr, int num) {
int less = 0;
int more = nodeArr.length;
int cur = 0;
while (cur != more) {
if (nodeArr[cur].value < num) {
swap(nodeArr, ++less, cur++);
} else if (nodeArr[cur].value > num) {
swap(nodeArr, --more, cur);
} else {
cur++;
}
}
}
public static void swap(Node[] arr, int i, int j) {
Node temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
进阶:
链表长度为N 时间复杂度达到o(N) 额外空间复杂度达到o(1)
我们要知道荷兰国旗问题是不能保证稳定性的
设置三个节点变量less equal more 为空 然后分别给这三个区域设置end 先是遍历一遍链表 找到第一个小于的节点 第一个等于的节点 第一个大于的节点 不存在的话还是空
在遍历一遍,发现小于num的(不是less),然后挂到less区域的end上面,发现等于num的但是不能是equal,然后挂到equal区域的end上面 大于同样如此
最后less区域的尾部和equal区域的头部相连,equal区域的尾部和more区域的头部相连
public static Node partition2(Node head, int num) {
Node SH = null; //小于部分头
Node ST = null; //小于部分尾
Node EH = null; //等于部分头
Node ET = null; //等于部分尾
Node MH = null; //大于部分头
Node MT = null; //大于部分尾
Node next = null; //保存下一个节点
while (head != null) {
next = head.next;
head.next = null;
if (head.value < num) { // 发货
if(SH == null) {
SH = head;
ST = head;
} else {
ST.next = head;
ST = head;
}
} else if (head.value == num) {
if (EH == null) {
EH = head;
ET = head;
} else {
ET.next = head;
ET = head;
}
} else {
if (MH == null) {
MH = head;
MT = head;
} else {
MT.next = head;
MT = head;
}
}
}
if (ST != null) { // 装货 -- 要考虑某个部分为空的情况
ST.next = EH;
ET = ET == null ? ST : ET;
}
if (ET != null) {
ET.next = MT;
}
return SH != null ? SH : EH != null ? EH : MH; //返回
}