P102 含随机指针的链表拷贝

描述#

这个题目说的是，给你一个单链表，链表上每个节点都包含一个随机指针，随机指针可能为空，也可能指向这条链表上任意节点。你要写一个函数，对这条链表进行深拷贝。

代码#

public class AlgoCasts {

  class RandomListNode {
    int val;
    RandomListNode next, random;

    RandomListNode(int x) {
      this.val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public RandomListNode copyListWithRandomPointer(RandomListNode head) {
    if (head == null) return null;
    Map<RandomListNode, RandomListNode> map = new HashMap<>();
    RandomListNode copyHead = new RandomListNode(head.val);
    map.put(head, copyHead);
    for (RandomListNode p = head.next, q = copyHead; p != null; p = p.next, q = q.next) {
      q.next = new RandomListNode(p.val);
      map.put(p, q.next);
    }
    for (RandomListNode p = head, q = copyHead; p != null; p = p.next, q = q.next) {
      if (p.random != null) {
        q.random = map.get(p.random);
      }
    }
    return copyHead;
  }

  // Time: O(n), Space: O(1)
  public RandomListNode copyListWithRandomPointerO1(RandomListNode head) {
    if (head == null) return null;
    for (RandomListNode p = head; p != null; p = p.next.next) {
      RandomListNode copy = new RandomListNode(p.val);
      copy.next = p.next;
      p.next = copy;
    }
    for (RandomListNode p = head; p != null; p = p.next.next) {
      if (p.random != null)
        p.next.random = p.random.next;
    }
    RandomListNode dummy = new RandomListNode(0);
    RandomListNode p = head, cp = dummy;
    while (p != null) {
      RandomListNode copy = p.next, next = p.next.next;
      cp.next = copy;
      cp = copy;
      p.next = next;
      p = next;
    }
    return dummy.next;
  }

}