剑指offer 25.复杂链表的复制

25.复杂链表的复制

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

好繁琐一道题，用了三次遍历，赋值的时候用了三目运算符缩短代码。

1. 在每个节点后增加一个新节点，只有节点本身。
2. 给每个新增节点增加random。
3. 分开两个链表。

代码

 public class RandomListNode {

  int label;
  RandomListNode next = null;
  RandomListNode random = null;

  RandomListNode(int label) {
    this.label = label;
  }
}

public RandomListNode Clone(RandomListNode pHead) {
  if (pHead == null) {
    return null;
  }
  RandomListNode cur = pHead;
  while (cur != null) {
    RandomListNode nextnode = cur.next;
    RandomListNode clone = new RandomListNode(cur.label);
    cur.next = clone;
    clone.next = nextnode;
    cur = nextnode;
  }
  cur = pHead;
  while (cur != null) {
    cur.next.random = cur.random == null ? null : cur.random.next;
    cur = cur.next.next;
  }
  cur = pHead;
  RandomListNode newHead = pHead.next;
  while (cur != null) {
    RandomListNode clone = cur.next;
    cur.next = clone.next;
    cur = cur.next;
    clone.next = clone.next == null ? null : clone.next.next;
  }
  return newHead;
}