Copy List with Random Pointer

描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

分析

无

代码

  1. // Copy List with Random Pointer
  2. // 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4.     public RandomListNode copyRandomList(RandomListNode head) {
  5.         for (RandomListNode cur = head; cur != null; ) {
  6.             RandomListNode node = new RandomListNode(cur.label);
  7.             node.next = cur.next;
  8.             cur.next = node;
  9.             cur = node.next;
  10.         }
  12.         for (RandomListNode cur = head; cur != null; ) {
  13.             if (cur.random != null)
  14.                 cur.next.random = cur.random.next;
  15.             cur = cur.next.next;
  16.         }
  18.         // 分拆两个单链表
  19.         RandomListNode dummy = new RandomListNode(-1);
  20.         for (RandomListNode cur = head, new_cur = dummy;
  21.                 cur != null; ) {
  22.             new_cur.next = cur.next;
  23.             new_cur = new_cur.next;
  24.             cur.next = cur.next.next;
  25.             cur = cur.next;
  26.         }
  27.         return dummy.next;
  28.     }
  29. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/copy-list-with-random-pointer.html