双指针单向链表的快速复制算法
更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南
有一种较为特殊的单向链表，如下：
这里写图片描述
这种链表一个特点是，除了next指向下一个节点外，它还多了一个指针jump,这个指针指向队列中的某一个节点,这个节点可以是当前节点自己，也可以是队列中的其他节点。例如上图，节点0的jump指针指向了最后一个节点，而节点1的jump指针指向了它自己。这种链表有一个专门的名称，叫Posting List.
要求，你设计一个算法，复制给定的一个Posting List。算法的时间复杂度是O(n), 算法除了运行分配赋值节点所需的内存外，不能分配多余内存，例如给定上面队列，你的算法智能多分配五个节点的内存。算法可以更改原队列，当更改后，需要将队列恢复原状。
这道题目有一定难度，难点在于如何复制jump指针。如果没有jump指针，那么复制一个单项链表是很容易的。我们先设想一个最简单的做法，先不考虑jump节点，先把单项队列复制出来，然后再考虑如何设置新队列节点的jump指针。
一个做法是，给定一个具体的节点，然后将队列遍历以便，判断jump节点与当前节点的距离，例如给定节点0，我们通过遍历得知，jump指向的节点，与当前节点有四个节点的距离，然后在新复制的队列中，从新赋值的节点0往后走4个节点，找到新拷贝的节点4，接着把新节点0的jump指针指向新生成的节点4.
上面做法有个问题就是，设置每个节点的jump指针时，都得将队列遍历一次，这样的话，整个算法复杂度会是 O(n^2).但题目要求，算法复杂度必须是O(n),由此，我们必须重新思考新的算法。
我的做法是这样的，首先遍历队列，为每个节点生成一个拷贝：
接着，把原节点的next指针指向对应的拷贝节点，拷贝节点的next指针指向原节点原来next指向的节点：
这里写图片描述
经过上面的变动，原节点跟它自己的拷贝连接了起来，同时原队列的连接性任然得以保持，例如图中，上面的节点0要抵达它的下一个节点，那么只需要通过next指针到达它的拷贝节点，也就是下面的节点0，然后再通过拷贝节点的next指针就可以抵达上面的节点1了。
此时，新节点的jump指针就容易设置了，例如要设置新拷贝的节点0的jump指针，先通过它原节点的jump指针，找到节点4，然后再通过节点4的next指针，找到节点4的拷贝节点，也就是上图下方的节点4，最后把拷贝节点0的 jump指针设置成对应的上图下方的节点4即可。如果用node来表示原节点，cpNode来表示对应的拷贝节点，下面代码就可以设置拷贝节点的jump指针：
cpNode = node.next; //获得拷贝节点
cpNode.jump = node.jump.next;
遍历原队列的每个节点，采取上面的操作，这样，新拷贝节点的jump指针就能够正确的设置了。
最后，恢复原队列以及设置拷贝节点的next指针。由于拷贝节点的next指针，指向原节点原来next指向的对象，由此只要把原节点的next设置为拷贝节点的next指向的对象，就可以复原原来的状态。拷贝节点0的next要想指向拷贝节点1，首先通过它自己的next，找到原节点1，也就是图中上方的节点1，然后通过原节点1的next找到对应的拷贝节点，也就是图中下方的节点1，于是把拷贝节点0的next指针就可以指向拷贝节点1，从而实现图中下方的节点0通过next指针指向拷贝节点1。实现代码如下：
cpNode = node.next; //获得拷贝节点
node.next = cpNode.next; //恢复原节点的next指针
node = node.next;
cpNode.next = node.next; //将当前拷贝节点的next指针指向下一个拷贝节点。
上面算法，每一步骤的时间复杂度都是o(n),同时我们只为新节点分配内存，除此只为，并没有多余的内存分配，因此，算法符合题目要求。我们看看具体的代码实现：
public class ListUtility {
private Node tail;
private Node head;
private int listLen = 0;
private int postingListLen = 0;
HashMap<Integer, PostingNode> map = new HashMap<Integer, PostingNode>();
PostingNode createPostingList(int nodeNum) {
if (nodeNum <= 0) {
return null;
}
postingListLen = nodeNum;
PostingNode postingHead = null, postingTail = null;
PostingNode postingNode = null;
int val = 0;
while (nodeNum > 0) {
if (postingNode == null) {
postingHead = new PostingNode();
postingHead.val = val;
postingNode = postingHead;
postingTail = postingHead;
} else {
postingNode.next = new PostingNode();
postingNode = postingNode.next;
postingNode.val = val;
postingNode.next = null;
postingTail = postingNode;
}
map.put(val, postingNode);
val++;
nodeNum--;
}
PostingNode tempHead = postingHead;
createJumpNode(tempHead);
return postingHead;
}
private void createJumpNode(PostingNode pHead) {
Random ra = new Random();
while (pHead != null) {
int n = ra.nextInt(postingListLen);
pHead.jump = map.get(n);
pHead = pHead.next;
}
}
public void printPostingList(PostingNode pHead) {
while (pHead != null) {
System.out.print("(node val:" + pHead.val + " jump val : " + pHead.jump.val + " ) ->");
pHead = pHead.next;
}
System.out.print(" null ");
}
....
}
上面的代码用于创建一个Posting list, 链表的复杂算法实现在类PostingList.java中，代码如下：
public class PostingList {
private PostingNode head ;
private PostingNode copyHead;
public PostingList(PostingNode node) {
this.head = node;
}
public PostingNode copyPostingList() {
createPostingNodes();
createJumpNodes();
ajustNextPointer();
return copyHead;
}
private void createPostingNodes() {
PostingNode node = null;
PostingNode tempHead = head;
while (tempHead != null) {
node = new PostingNode();
node.next = tempHead.next;
node.val = tempHead.val;
tempHead.next = node;
tempHead = node.next;
}
}
private void createJumpNodes() {
PostingNode temp = head;
copyHead = temp.next;
while (temp != null) {
PostingNode cpNode = temp.next;
cpNode.jump = temp.jump.next;
temp = cpNode.next;
}
}
private void ajustNextPointer() {
PostingNode temp = head;
while (temp != null) {
PostingNode cpNode = temp.next;
temp.next = cpNode.next;
temp = temp.next;
if (temp != null) {
cpNode.next = temp.next;
} else {
cpNode.next = null;
}
}
}
}
createPostingNodes 执行的是步骤1，它为每一个节点生成一个拷贝。
createJumpNodes 执行步骤2，它为每一个拷贝节点设置他们对应的jump指针
ajustNextPointer 执行步骤3，它调整原队列节点的next指针，以及设置拷贝节点的next指针。
每个函数里，只包含一个while循环，用于遍历队列，因此算法实现的复杂度是o(n).具体的代码讲解和调试演示过程，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
