【Offer】[35] 【复杂链表的复制】

• 题目描述
• 思路分析
• 测试用例
• Java代码
• 代码链接

题目描述

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

牛客网刷题地址

思路分析

1. 第一步，可以将复制原始链表上的每个节点，并链接起来，第二步，设置每个节点的特殊指针，这种思路需要O(n^{2)的时间复杂度}
2. 空间换时间。第一步和上面的一样，不过在我们要把原始节点和复制的节点放在哈希表中；第二步，由于有了哈希表，我们可以在O(1)的时间内根据哈希表找到特殊指针

3. 第三种方法：

   • 第一步复制链表，并将其连接在原始节点的后面

   

   

   • 第二步连接节点的特殊指针，复制的节点的特殊指针指向原始节点特殊指针的下一个结点

   

   

   • 第三步重新连接链表，将原始链表和复制的链表节点分开

测试用例

1. 功能测试：节点中的m pSibling 指向节点自身;两个节点的m pSibling形成环状结构;链表中只有一个节点。
2. 特殊输入测试：指向链表头节点的指针为nullptr指针。

Java代码

public class Offer35 {
    public static void main(String[] args) {
        test1();
        test2();
        test3();    }    public static  RandomListNode Clone(RandomListNode pHead)
    {
        return Solution1(pHead);    }    private static  RandomListNode Solution1(RandomListNode pHead) {
        cloneNodes(pHead);
        connectSlibNodes(pHead);
        return reconnectNodes(pHead);
    }     private static void cloneNodes(RandomListNode pHead){
            RandomListNode pNode = pHead;
            while(pNode!=null){
                RandomListNode pClonedNode = new RandomListNode(pNode.label);
                pClonedNode.next = pNode.next;
                pClonedNode.random = null;
                pNode.next = pClonedNode;
                pNode = pClonedNode.next;
            }        }
        private static void connectSlibNodes(RandomListNode pHead){
            RandomListNode pNode = pHead;
            while(pNode!=null){
                RandomListNode pClonedNode = pNode.next;
                if(pNode.random!=null){
                     pClonedNode.random = pNode.random.next;
                }
                pNode = pClonedNode.next;
            }
        }
        private  static RandomListNode reconnectNodes(RandomListNode pHead){
            RandomListNode pNode = pHead;
            RandomListNode pClonedHead = null;
            RandomListNode pClonedNode = null;
            if(pNode!=null){
                pClonedHead = pClonedNode = pNode.next;
                pNode.next = pClonedNode.next;
                pNode = pClonedNode.next;
            }
            while(pNode!=null){
                pClonedNode.next = pNode.next;
                pClonedNode = pClonedNode.next;
                pNode.next = pClonedNode.next;
                pNode = pNode.next;
            }
            return pClonedHead;
        }    private static void test1() {    }    private static void test2() {    }
    private static void test3() {    }}

代码链接

剑指Offer代码-Java