当前位置：首页 > news >正文

【算法】将单向链表按某值分成左边小、中间相等、右边大的形式

news 2024/10/22 15:26:40

前置知识

数据结构：链表
测试链接:链表划分
本题考察对链表coding速度的熟练度。也考察读者对链表分块的处理，另外，透过此题可以窥探链表快速排序的实现。

题目

给定一个单向链表的头节点head, 节点的值是int类型。给定任意整数pivot。实现这样一个函数。将原链表调整为左部分都＜pivot, 中间部分都是值等于pivot，右部分都是值大于pivot的节点。
举例:
[9->3->4->5->1->2->3->null], pivot = 3
处理后:
[1->2->3->3->4->5->9->null]

【解法1：容器法->数组】

理解此法需要一点基础，双向快速排序：荷兰国旗快排法

链表节点存储到数组：首先将链表的节点存储到一个数组中，这样可以运用数组快速排序算法中的partition操作。
三向划分快速排序：该排序方法适合处理包含重复键值的场景，将链表按照枢纽值pivot分为小于、等于和大于三部分，改善了排序的效率。
数组到链表的转换：排序完成，将数组中的节点按顺序连接好，还原成一个链表。
注意：下面的写法不能通过力扣的题目，因为我们用了类似快速排序的partition操作，由于快排是不具有稳定性的，所以三向划分或者简单二向划分都没办法保持相对顺序不变。

//不要提交这个类
class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}class Solution {public static int MAX = 201;  // 预定义的数组最大长度public static ListNode[] nodeArr = new ListNode[MAX];  // 存储链表节点的数组public static int n;  // 链表节点的实际数量// 对数组中的元素进行三向划分排序，以pivot为中心public static void arrPartition(int pivot) {int small = -1;  // 记录小于pivot的最后一个元素的位置int big = n;  // 记录大于pivot的第一个元素的位置int i = 0;  // 当前考察的元素的索引while (i != big) {if (nodeArr[i].val < pivot) {swap(++small, i++);  // 将小于pivot的元素移动到前面} else if (nodeArr[i].val == pivot) {i++;  // 遇到等于pivot的元素，仅向后移动索引} else {// nodeArr[i].val > pivotswap(--big, i);  // 将大于pivot的元素移动到后面}}}// 交换数组中两个指定索引的元素public static void swap(int i, int j) {ListNode temp = nodeArr[i];nodeArr[i] = nodeArr[j];nodeArr[j] = temp;}// 对链表进行分区，使得小于pivot的节点都在前，等于pivot的节点在中间，大于pivot的节点在后public ListNode partition(ListNode head, int pivot) {if (head == null) {return head;  // 如果头节点为空，直接返回null}ListNode cur = head;int i = 0// 遍历链表，计算节点数while (cur != null) {i++;cur = cur.next;}n = i;  // 更新链表的节点总数cur = head;// 将链表的节点存储到数组中for (i = 0; i < n; i++) {nodeArr[i] = cur;cur = cur.next;}// 调用排序函数对节点数组进行排序arrPartition(pivot);// 将排序后的数组元素重新链接成链表for (i = 1; i < n; i++) {nodeArr[i - 1].next = nodeArr[i];}nodeArr[i - 1].next = null;  // 确保链表的最后一个节点的next指向nullreturn nodeArr[0];  // 返回重新排序后的链表的头节点}
}

不能保持相对顺序不变，只能过这些测试用例了。
在这里插入图片描述

//二向划分， <pivot | >=pivot，没有额外处理重复值的情况。 因为其本身是不稳定的。
public static void arrPattition(int pivot) {int small = -1;int i = 0;while(i!=n) {if(nodeArr[i].val < pivot) {swap(++small,i++);}else {//nodeArr[i].val >= pivoti++;}}}

【解法2：链表分组和合并】

链表分离：将原链表中的所有节点依次划分进3个链表， 3个链表分别为small, equal, big三部分。
比如:[2->3->7->5->2->6->4->null], pivot = 4。
small:[2->3->2->null]
equal:[4->null]
big:[7->5->6->null]
将三种链表进行合并。small->equal->big的顺序合并
注意:由于三者可能存在其中为空表的情况，因此连接时需要讨论，而且要对返回的头节点进行讨论处理。
对重复的部分有处理，正确的写法，但不满足力扣的题目要求。

//不要提交这个类
public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}public static ListNode partition(ListNode head, int pivot) {// 初始化三个部分的头和尾节点指针ListNode smallHead = null, smallTail = null;ListNode equalHead = null, equalTail = null;ListNode bigHead = null, bigTail = null;ListNode next = null; // 用于保存遍历中当前节点的下一个节点// 遍历原始链表while (head != null) {next = head.next; // 保存当前节点的下一个节点head.next = null; // 断开当前节点与链表的连接，便于单独处理// 根据节点值与pivot的关系，将节点分配到对应的部分if (head.val < pivot) {// 小于pivot的部分if (smallTail == null) {smallHead = smallTail = head;} else {smallTail.next = head;smallTail = smallTail.next;}} else if (head.val == pivot) {// 等于pivot的部分if (equalTail == null) {equalHead = equalTail = head;} else {equalTail.next = head;equalTail = equalTail.next;}} else {// 大于pivot的部分if (bigTail == null) {bigHead = bigTail = head;} else {bigTail.next = head;bigTail = bigTail.next;}}head = next; // 移动到下一个节点}// 连接三个部分if (smallTail != null) {smallTail.next = equalHead; // 小于部分的尾连等于部分的头equalTail = equalTail == null ? smallTail : equalTail; // 更新等于部分的尾指针}if (equalTail != null) {equalTail.next = bigHead; // 等于部分的尾连大于部分的头}// 根据是否存在小于部分或等于部分返回合适的头节点return smallHead == null ? (equalHead == null ? bigHead : equalHead) : smallHead;
}

能过力扣的写法，不能包含对重复部分的特殊处理。

public static ListNode partition(ListNode head, int pivot) {// 初始化ListNode smallHead = null, smallTail = null;ListNode bigHead = null, bigTail = null;ListNode next = null; // 用于保存遍历中当前节点的下一个节点// 遍历原始链表while (head != null) {next = head.next; // 保存当前节点的下一个节点head.next = null; // 断开当前节点与链表的连接，便于单独处理// 根据节点值与pivot的关系，将节点分配到对应的部分if (head.val < pivot) {// 小于pivot的部分if (smallTail == null) {smallHead = smallTail = head;} else {smallTail.next = head;smallTail = smallTail.next;}} else {// 大于等于pivot的部分if (bigTail == null) {bigHead = bigTail = head;} else {bigTail.next = head;bigTail = bigTail.next;}}head = next; // 移动到下一个节点}if(smallTail != null) {smallTail.next = bigHead;}return smallHead == null ? bigHead : smallHead;}