剑指Offer-复杂链表的复制

太过爱你忘了你带给我的痛 2022-02-25 11:14 185阅读 0赞

## 题目描述 ##

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路—**三步法**：一看到题目有点蒙，复制链表，想着直接新建个头指针等于链表头指针就行了。题目左侧给的示例也是空白的，并没有任何东西！实际上**题目本意**是：**不使用题目给出的链表中的所有结点，你需要重新创建一个链表，同时链表结构要与题目中给出的链表结构一致。** 这个三步法是最容易理解且操作的方法，**先将链表中每个结点都复制一遍，依次插入原结点的后面（如原来是A->B->C 变成A->A’->B->B’->C->C’），然后从头开始遍历，在复制的结点上实现原链表的结构，最后再将复制的链表结点拆出来。**

> **这里有两点需要非常注意！**  
> 1.一定要注意判断链表是否为空，特别是连续.next.next的时候  
> 2.将复制链表从原链表中拆出时，要还原原链表结构！原链表节点不能和复制结点有连接！要不然提交代码会一直显示你的结果为空！

解题思路—**哈希表**：推荐使用**哈希表**！使用哈希表复制存储链表，即变相的将链表拆分，这样复制链表结点会更加的方便，结点复制完成后，直接将复制的结点链接起来即可，比上面的三步法更加简洁！

## Java解题—三步法 ##

/*
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;
    
        RandomListNode(int label) {
            this.label = label;
        }
    }
    */
    public class Solution {
        public RandomListNode Clone(RandomListNode pHead)
        {
            if(pHead==null)
                return null;
            RandomListNode dummyhead = pHead;
            while(pHead!=null){
                RandomListNode clonenode = new RandomListNode(pHead.label);
                clonenode.next = pHead.next;
                pHead.next = clonenode;
                pHead = clonenode.next;
            }
            pHead = dummyhead;
            while(pHead!=null){
                pHead.next.random = pHead.random==null?null:pHead.random.next;
                pHead = pHead.next.next;
            }
            pHead = dummyhead;
            RandomListNode result = pHead.next;
            dummyhead = dummyhead.next;
            while(pHead!=null){
                pHead.next = pHead.next.next;
                if(dummyhead.next!=null)
                    dummyhead.next = dummyhead.next.next;
                dummyhead = dummyhead.next;
                pHead = pHead.next;
            }
            return result;
        }
    }

## Java解题—哈希表 ##

import java.util.HashMap;
    public class Solution {
        public RandomListNode Clone(RandomListNode pHead)
        {
            HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
            RandomListNode cur = pHead;
            // 复制链表节点
            while (cur != null) {
                map.put(cur, new RandomListNode(cur.label));
                cur = cur.next;
            }
            // 链接复制的节点
            cur = pHead;
            while (cur != null) {
                map.get(cur).next = map.get(cur.next);
                cur = cur.next;
            }
            RandomListNode resHead = map.get(pHead); // 头结点
            cur = pHead;
            // 链接random的节点
            while (cur != null) {
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return resHead;
        }
    }