算法 （十）链表相关：将单向链表按某值划分成左边小、中间相等、右边大的形式

这篇博文写得很好：将单链表按某值划分成左边小，中间相等，右边大的形式

---

1、将单向链表按某值划分成左边小、中间相等、右边大的形式

1.1 描述

有两种方法

1. 第一种：将链表数据存储到数组中（这里直接建立Node数组），然后用快排的思路（荷兰国旗问题）将数据分成三部分，然后再连接成链表（快排得partion思路是不稳定得，也就是说排序后不能保证原来的数据相对位置不变）
2. 第二种：建立三个小链表，small，equal，bigger，然后选派节点到这三个链表中，最后将三个链表连接起来

第一种要用到额外辅助结构–数组，O(N),第二种直接就是O(1)

代码实现：

package cn.nupt;

/**
 * @Description: 将单向链表按某值划分成左边小、中间相等、右边大的形式
 *
 * @author PizAn
 * @Email [e-mail]
 * @date 2019年2月19日 下午1:35:07
 * 
 */
public class SmallerEqualBigger {

	// 两种方法，第一种：将链表数据存储到数组中（这里直接建立Node数组），然后用快排的思路（荷兰国旗问题）将数据分成三部分，然后再连接成链表
	// 第二种：建立三个小链表，small，equal，bigger，然后选派节点到这三个链表中，最后将三个链表连接起来
	// 第一种要用到额外辅助结构--数组，O(N),第二种直接就是O(1),

	// 构建链表结构
	public static class Node {
		int value;
		Node next;

		public Node(int value) {
			this.value = value;
		}
	}

	// 第一种：将链表数据存储到数组中（这里直接建立Node数组），然后用快排的思路（荷兰国旗问题）将数据分成三部分，然后再连接成链表
	public static Node smallerEqualBigger01(Node head, int k) {

		if (head == null) {
			return head;
		}

		// 1、先拿到链表的长度
		int ListNum = 0;
		Node cur1 = head;// 这里用一个临时的Node变量来代替head，因为head不能变
		while (cur1 != null) {
			ListNum++;
			cur1 = cur1.next;

		}

		// 2、创建和链表长度一样的数组（数据类型是Node）
		Node[] arr = new Node[ListNum];
		Node cur2 = head;// 这里也可以直接用上面的cur1=head，这里为了方便看代码，就重新创建新的临时变量代替head

		// 3、将链表的节点存储到数组中
		for (int i = 0; i < arr.length; i++) {
			arr[i] = cur2;
			cur2 = cur2.next;

		}

		// 4、对数组进行快排partition操作
		partition(arr, k);

		// 5、然后再次将数组变成链表

		for (int i = 0; i < arr.length - 1; i++) {
			arr[i].next = arr[i + 1];
		}

		arr[arr.length - 1].next = null;

		return arr[0];

	}

	private static void partition(Node[] arr, int k) {
		// 思路：三个变量，less=-1和more=arr.length,和一个指示变量index都是在数组左右的外面的点

		int less = -1;
		int more = arr.length;
		int index = 0;
		while (index < more) { // 这个地方是跟more挂钩的，因为more也在缩小！！！

			if (arr[index].value < k) { // 偏小，和less后面一个数交换
				swap(arr, ++less, index++);
			} else if (arr[index].value > k) { // 偏大，和more前面一个数交换
				// 注意：这个地方index没有++，因为从--more换来的数还不知道是不是比k小，还需要再来一次循环比较！！！！！
				swap(arr, --more, index);

			} else {
				index++;
			}

		}

	}

	// 交换函数
	private static void swap(Node[] arr, int i, int j) {
		Node temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;

	}

	// 第二种：建立三个小链表，small，equal，bigger，然后选派节点到这三个链表中，最后将三个链表连接起来
	public static Node smallerEqualBigger02(Node head, int k) {

		// 1、建立三个链表，分别是small、equal、bigger的第一个head和最后一个last节点

		Node sH = null;
		Node sL = null;

		Node eH = null;
		Node eL = null;

		Node bH = null;
		Node bL = null;

		while (head != null) {

			if (head.value < k) { // 节点值小于k，放到samll里面
				if (sH == null) { // small里面没有数,则全部初始化为head
					sH = head;
					sL = head;
				} else { // small里面有数,就把这个节点加到sL下面，然后调整sL的位置
					sL.next = head;
					sL = head;
				}
			} else if (head.value == k) { // 节点值等于k，放到equal里面
				if (eH == null) {
					eH = head;
					eL = head;
				} else {
					eL.next = head;
					eL = head;
				}

			} else {// 节点值大于k，放到bigger里面
				if (bH == null) {
					bH = head;
					bL = head;
				} else {
					bL.next = head;
					bL = head;
				}
			}

			// 更新节点，往后走
			head = head.next;

		}

		// 连接三个链表
		if (sL != null) {
			sL.next = eH;
			eL = eL == null ? sL : eL;
		}

		if (eL != null) {
			eL.next = bH;
		}

		// 使得合并后的链表最后一个节点指向空
		if (bL != null) {
			bL.next = null;
		} else if (eL != null) {
			eL.next = null;

		} else {
			sL.next = null;
		}
		
		//返回头节点
		return sH != null ? sH : (eH != null ? eH : bH);

	}

	// 打印链表
	public static void printLinkedList(Node node) {
		System.out.print("Linked List: ");
		while (node != null) {
			System.out.print(node.value + " ");
			node = node.next;
		}
		System.out.println();
	}

	//测试主函数
	public static void main(String[] args) {
		Node head1 = new Node(7);
		head1.next = new Node(9);
		head1.next.next = new Node(1);
		head1.next.next.next = new Node(8);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(2);
		head1.next.next.next.next.next.next = new Node(5);
		printLinkedList(head1);
		// head1 = smallerEqualBigger01(head1, 4);
		head1 = smallerEqualBigger02(head1, 4);
		// head1 = listPartition2(head1, 5);
		printLinkedList(head1);

	}

}


测试结果：

Linked List: 7 9 1 8 5 2 5 
Linked List: 1 2 7 9 8 5 5