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

前置知识

• 数据结构：链表

• 测试链接:链表划分

• 本题考察对链表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：容器法->数组】

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

1. 链表节点存储到数组：首先将链表的节点存储到一个数组中，这样可以运用数组快速排序算法中的partition操作。
2. 三向划分快速排序：该排序方法适合处理包含重复键值的场景，将链表按照枢纽值pivot分为小于、等于和大于三部分，改善了排序的效率。
3. 数组到链表的转换：排序完成，将数组中的节点按顺序连接好，还原成一个链表。
   注意：下面的写法不能通过力扣的题目， 因为我们用了类似快速排序的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 > pivot
                swap(--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指向null
        return 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 >= pivot
				i++;
			}
		}
	}

【解法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;
	}

一切的努力都赢来了最好的成果。

时间复杂度: O ( n ) O(n) O(n).
空间复杂度: O ( 1 ) O(1) O(1).

每日两题结束。