力扣原题,链表面试题之复制带随机指针的链表

简介: 力扣原题,链表面试题之复制带随机指针的链表

一种特殊的单链表节点类型描述如下:

public static class Node{
    public int value;
    public Node next;
    public Node rand;
    public Node(int v) {
      value=v;
    }
  }

rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。要求:时间复杂度O(N),额外空间复杂度O(1),注意,无环是指next方向上是无环的!!!

方法一(笔试用,最简单):在next方向上正常遍历一遍链表,遍历过程种将每个结点克隆存入HashMap<Node,Node>,表中的key是老结点,value是克隆的结点。就是人为构造一种对应关系,之后再遍历一遍链表,便可实现,具体看下面代码。但是这种方法在空间复杂度上没有做到O(1)

方法二(面试用):额外空间复杂度O(1),具体看代码

package com.harrison.class06;
import java.util.HashMap;
public class Code04_CopyListWithRandom {
  public static class Node {
    public int value;
    public Node next;
    public Node rand;
    public Node(int v) {
      value = v;
    }
  }
  public static Node copyRandomList1(Node head) {
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    Node cur = head;
    while (cur != null) {
      map.put(cur, new Node(cur.value));
      cur = cur.next;
    }
    cur = head;
    while (cur != null) {
      // cur (key)老结点 map.get(cur) (value)新结点
      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 copyRandomList2(Node head) {
    if (head == null) {
      return null;
    }
    // 1 -> 2 -> 3 -> null
    // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
    Node cur = head;// 老结点
    Node next = null;// 老结点的下一个结点
    while (cur != null) {
      next = cur.next;// next记住老结点的下一个结点
      cur.next = new Node(cur.value);// 当前的老结点指向 复制自己的结点
      cur.next.next = next;// 复制的结点指向 next
      cur = next;
    }
    cur = head;
    Node copy = null;// 复制的结点
    // 依次设置 1' 2' 3' 的rand指针
    while (cur != null) {
      next = cur.next.next;// next 记住老结点的下一个结点
      copy = cur.next;// copy 来到(第一个)复制的结点
      // copy结点的rand指针指向 老结点的rand指针指向的结点的next指针
      copy.rand = cur.rand != null ? cur.rand.next : null;
      cur = next;// 当前结点往下跳
    }
    Node res = head.next;// 记住复制后的链表的头结点
    cur = head;
    // next方向上,把新老链表分离,rand方向不要动
    while (cur != null) {
      next = cur.next.next;// next 记住老结点的下一个结点
      copy = cur.next;// copy 来到(第一个)复制的结点
      // copy结点的next指针指向 下一个老结点的next指针
      copy.next = next != null ? next.next: null;
      cur = next;// 当前结点往下跳
    }
    return res;
  }
  public static void printLinkedList(Node node) {
    System.out.print("Linked List:");
    while (node != null) {
      System.out.print(node.value + " ");
      node = node.next;
    }
    System.out.println();
  }
  public static void main(String[] args) {
    Node head1 = new Node(7);
    head1.next = new Node(9);
    head1.next.next = new Node(1);
    head1.next.next.next = new Node(8);
    head1.next.next.next.next = new Node(5);
    head1.next.next.next.next.next = new Node(2);
    head1.next.next.next.next.next.next = new Node(5);
    printLinkedList(head1);
    //head1=copyRandomList1(head1);
    head1 = copyRandomList2(head1);
    printLinkedList(head1);
  }
}
相关文章
|
2天前
|
存储 C语言
用指针处理链表
用指针处理链表
11 3
|
2天前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
2天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2天前
|
存储 算法 索引
链表面试题
链表面试题
链表面试题
|
2天前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
3天前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
|
4天前
|
存储 缓存 搜索推荐
指针链表
指针链表
11 0
|
4天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
10 0