【题目】
给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。
实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
笔试：构建一个Node型数组，将单链表中的节点添加进数组中，在数组中进行操作，再把数组中的每一个Node窜起来
面试：用6个变量来实现，没有用额外的空间
package Algorithms; /** * @author : zhang * @version : 1.0 * @date : Create in 2021/8/10 * @description : */ public class SmallerEqualBigger { 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); //Linked List: 7 9 1 8 5 2 5 // head1 = listPartition1(head1, 5); head1 = listPartition2(head1, 5); printLinkedList(head1); //Linked List: 1 2 5 5 7 9 8 } public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } //方式1：笔试 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类型的数组 Node[] nodeArr = new Node[i]; cur = head; //for循环添加单链表中的Node进数组 for (i = 0; i != nodeArr.length; i++) { nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr, pivot); //将数组中的Node进行首尾串联 for (i = 1; i != nodeArr.length; i++) { nodeArr[i - 1].next = nodeArr[i]; } nodeArr[i - 1].next = null; return nodeArr[0]; } //数组中进行Partition操作（< = >） public static void arrPartition(Node[] nodeArr, int pivot) { int small = -1; int big = nodeArr.length; //big = 7 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; } //方式2：面试 public static Node listPartition2(Node head, int pivot) { Node sH = null; // small head Node sT = null; // small tail Node eH = null; // equal head Node eT = null; // equal tail Node bH = null; // big head Node bT = null; // big tail Node next = null; // save next node // every node distributed to three lists while (head != null) { next = head.next; head.next = null; if (head.value < pivot) { if (sH == null) { sH = head; sT = head; } else { sT.next = head; sT = head; } } else if (head.value == pivot) { if (eH == null) { eH = head; eT = head; } else { eT.next = head; eT = head; } } else { if (bH == null) { bH = head; bT = head; } else { bT.next = head; bT = head; } } head = next; } // small and equal reconnect if (sT != null) { //如果有小于区域 sT.next = eH; eT = eT == null ? sT : eT; //下一步，谁去连大于区域的头，谁就变成eT } // all reconnect if (eT != null) { eT.next = bH; } 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(); } }