一定要早日上岸鸭 · July 22, 2021 0

138. 复制带随机指针的链表

138. 复制带随机指针的链表

类似于 133. 克隆图 但是由于random节点的存在不能够直接找random的节点。这里用了拆分链表的方法:

  1. 创建小弟节点
  2. 链接random节点
  3. 拆分大哥小弟
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { // 复制小弟: for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next.next){ Node youngBrother = new Node(oldBrother.val); youngBrother.next = oldBrother.next; oldBrother.next = youngBrother; } // 复制random结点: for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next.next){ if(oldBrother.random!=null) oldBrother.next.random = oldBrother.random.next; } // 拆分大哥小弟两链表: Node dummy = new Node(-1), cur = dummy; for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next){ Node youngBrother = oldBrother.next; cur = cur.next = youngBrother; oldBrother.next = youngBrother.next; } return dummy.next; } }