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

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

【题目】

给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。

例如：链表9->0->4->5->1，pivot=3。

调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。

进阶：

在原问题的要求之上再增加如下两个要求。

●　在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。

例如：链表9->0->4->5->1，pivot=3。调整后的链表是0->1->9->4->5。在满足原问题要求的同时，左部分节点从左到右为0、1。在原链表中也是先出现0，后出现1；中间部分在本例中为空，不再讨论；右部分节点从左到右为9、4、5。在原链表中也是先出现9，然后出现4，最后出现5。

●　如果链表长度为N ，时间复杂度请达到O (N )，额外空间复杂度请达到O (1)。

【难度】

尉　★★☆☆

【解答】

普通解法的时间复杂度为O (N )，额外空间复杂度为O (N )，就是把链表中的所有节点放入一个额外的数组中，然后统一调整位置的办法。具体过程如下：

1．先遍历一遍链表，为了得到链表的长度，假设长度为N 。

2．生成长度为N 的Node类型的数组nodeArr，然后遍历一次链表，将节点依次放进nodeArr中。本书在这里不用LinkedList或ArrayList等Java提供的结构，因为一个纯粹的数组结构比较利于步骤3的调整。

3．在nodeArr中把小于pivot的节点放在左边，把相等的放中间，把大于的放在右边。也就是改进了快速排序中partition的调整过程，即如下代码中的arrPartition方法。实现的具体解释请参看本书“数组类似partition的调整”问题，这里不再详述。

4．经过步骤3的调整后，nodeArr是满足题目要求的节点顺序，只要把nodeArr中的节点依次重连起来即可，整个过程结束。

全部过程请参看如下代码中的listPartition1方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public 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[] nodeArr = new Node[i]; i = 0; cur = head; for (i = 0; i ! = nodeArr.length; i++) { nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr, pivot); for (i = 1; i ! = nodeArr.length; i++) { nodeArr[i - 1].next = nodeArr[i]; } nodeArr[i - 1].next = null; return nodeArr[0]; } public void arrPartition(Node[] nodeArr, int pivot) { int small = -1; int big = nodeArr.length; 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 void swap(Node[] nodeArr, int a, int b) { Node tmp = nodeArr[a]; nodeArr[a] = nodeArr[b]; nodeArr[b] = tmp; }

下面来看看增加要求之后的进阶解法。对每部分都增加了节点顺序要求，同时时间复杂度仍然为O (N )，额外空间复杂度为O (1)。既然额外空间复杂度为O (1)，说明实现时只能使用有限的几个变量来完成所有的调整。

进阶解法的具体过程如下：

1．将原链表中的所有节点依次划分进三个链表，三个链表分别为small代表左部分，equal代表中间部分，big代表右部分。

例如，链表7->9->1->8->5->2->5，pivot=5。在划分之后，small、equal、big分别为：

small:1->2->null

equal:5->5->null

big:7->9->8->null

2．将small、equal和big三个链表重新串起来即可。

3．整个过程需要特别注意对null节点的判断和处理。

进阶解法还是主要考查面试者利用有限几个变量调整链表的代码实现能力，全部进阶解法请参看如下代码中的listPartition2方法。

public static Node listPartition2(Node head, int pivot) { Node sH = null; // 小的头 Node sT = null; // 小的尾 Node eH = null; // 相等的头 Node eT = null; // 相等的尾 Node bH = null; // 大的头 Node bT = null; // 大的尾 Node next = null; // 保存下一个节点 // 所有的节点分进三个链表中 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; } // 小的和相等的重新连接 if (sT ! = null) { sT.next = eH; eT = eT == null ? sT : eT; } // 所有的重新连接 if (eT ! = null) { eT.next = bH; } return sH ! = null ? sH : eH ! = null ? eH : bH; }

复制含有随机指针节点的链表

【题目】

一种特殊的链表节点类描述如下：

public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } }

Node类中的value是节点值，next指针和正常单链表中next指针的意义一样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。

给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。例如：链表1->2->3->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。复制后的链表应该也是这种结构，比如，1′->2′->3′->null，1′的rand指针指向3′，2′的rand指针指向null，3′的rand指针指向1′，最后返回1′。

进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为O (N )内完成原问题要实现的函数。