【题目】一种特殊的单链表节点类描述如下
class Node{ int value; Node next; Node rand; Node(int val){ value = val; } }
rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。
【要求】时间复杂度0(N),额外空间复杂度0(1)
解法:
一、利用额外空间 哈希表
1、新建一个哈希表,以老链表的Node为key,值为对应copy的Node
2、处理next指针
3、处理rand指针
二、不利用额外空间
1、生成克隆节点,放在老链表的下一个,然后克隆节点去窜上老链表的下一个
2、设置rand指针
把1和克隆的1单独拿出来,通过1找出rand指针的指向的Node节点,Node.next就是克隆的Node,让克隆出来的1的rand指针指向克隆出来的Node。依次类推
3、分离新老链表
代码
package Algorithms; /** * @author : zhang * @version : 1.0 * @date : Create in 2021/8/11 * @description : */ import java.util.HashMap; public class CopyListWithRandom { public static class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } //笔试 额外空间 哈希表 public static Node copyListWithRand1(Node head) { HashMap<Node, Node> map = new HashMap<Node, Node>(); Node cur = head; //1、循环往map中克隆Node,以老Node为key,value为对应copy的Node while (cur != null) { map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; //2、处理next指针与rand指针 while (cur != null) { //cur老 map.get(cur) 新 //cur.next为链表中Node的下一个节点, // 找出来作为key,在map中查找的value就是新Node【map.get(cur).next)】的next所要指向的节点 map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); } //面试:不利用额外空间 public static Node copyListWithRand2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; //1、 copy node and link to every node //例 【1 ->2 】 -> 【1 -> 1‘ -> 2 -> 2‘】 while (cur != null) { next = cur.next; //next保存cur的下一个节点 cur.next = new Node(cur.value); //cur的下一个Node指向新克隆的Node cur.next.next = next; //新克隆的Node的下一个节点指向next cur = next;//cur后移,然后重复以上操作 } cur = head; Node curCopy = null; //2、 set copy node rand while (cur != null) { next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } Node res = head.next; cur = head; //3、 split while (cur != null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res; } public static void printRandLinkedList(Node head) { Node cur = head; System.out.print("order: "); while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); cur = head; System.out.print("rand: "); while (cur != null) { System.out.print(cur.rand == null ? "- " : cur.rand.value + " "); cur = cur.next; } System.out.println(); } public static void main(String[] args) { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.rand = head.next.next.next.next.next; // 1 -> 6 head.next.rand = head.next.next.next.next.next; // 2 -> 6 head.next.next.rand = head.next.next.next.next; // 3 -> 5 head.next.next.next.rand = head.next.next; // 4 -> 3 head.next.next.next.next.rand = null; // 5 -> null head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4 System.out.println("原链表为:"); printRandLinkedList(head); Node res1 = copyListWithRand1(head); System.out.println("【方式1】copy的链表为:"); printRandLinkedList(res1); Node res2 = copyListWithRand2(head); System.out.println("【方式2】copy的链表为:"); printRandLinkedList(res2); System.out.println("原链表为:"); printRandLinkedList(head); } } /** * 原链表为: * order: 1 2 3 4 5 6 * rand: 6 6 5 3 - 4 * 【方式1】copy的链表为: * order: 1 2 3 4 5 6 * rand: 6 6 5 3 - 4 * 【方式2】copy的链表为: * order: 1 2 3 4 5 6 * rand: 6 6 5 3 - 4 * 原链表为: * order: 1 2 3 4 5 6 * rand: 6 6 5 3 - 4 */