剑指Offer面试题:24.复杂链表的复制

一、题目:复杂链表的复制

题目:请实现函数ComplexListNode Clone(ComplexListNode head),复制一个复杂链表。在复杂链表中,每个结点除了有一个Next指针指向下一个结点外,还有一个Sibling指向链表中的任意结点或者NULL。

  结点的定义如下,采用C#语言描述:

    public class ComplexListNode
    {
        public int Data { get; set; }
        public ComplexListNode Next { get; set; }
        public ComplexListNode Sibling { get; set; }

        public ComplexListNode(int data)
        {
            this.Data = data;
        }

        public ComplexListNode(int data, ComplexListNode next, ComplexListNode sibling = null)
        {
            this.Data = data;
            this.Next = next;
            this.Sibling = sibling;
        }
    }

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

二、解题思路

2.1 O(n2)的普通解法

  第一步是复制原始链表上的每一个结点,并用Next节点链接起来;

  第二步是设置每个结点的Sibling节点指针。

对于一个含有n个结点的链表,由于定位每个结点的Sibling都需要从链表头结点开始经过O(n)步才能找到,因此这种方法的总时间复杂度是O(n2)

2.2 借助辅助空间的O(n)解法

  第一步仍然是复制原始链表上的每个结点N创建N',然后把这些创建出来的结点用Next链接起来。同时我们把<N,N'>的配对信息放到一个哈希表中。

  第二步还是设置复制链表上每个结点的m_pSibling。由于有了哈希表,我们可以用O(1)的时间根据S找到S'

此方法使用空间换时间。对于有n个结点的链表我们需要一个大小为O(n)的哈希表,也就是说我们以O(n)的空间消耗把时间复杂度由O(n2)降低到O(n)

2.3 不借助辅助空间的O(n)解法

  第一步仍然是根据原始链表的每个结点N创建对应的N'。(把N'链接在N的后面)

    private static void CloneNodes(ComplexListNode head)
    {
        ComplexListNode node = head;
        while (node != null)
        {
            ComplexListNode cloned = new ComplexListNode();
            cloned.Data = node.Data;
            cloned.Next = node.Next;
            cloned.Sibling = null;

            node.Next = cloned;
            node = cloned.Next;
        }
    }

  第二步设置复制出来的结点的Sibling。(把N'的Sibling指向N的Sibling)

    private static void ConnectSiblingNodes(ComplexListNode head)
    {
        ComplexListNode node = head;
        while (node != null)
        {
            ComplexListNode cloned = node.Next;
            if (node.Sibling != null)
            {
                cloned.Sibling = node.Sibling;
            }
            node = cloned.Next;
        }
    }

  第三步把这个长链表拆分成两个链表:把奇数位置的结点用Next链接起来就是原始链表,偶数数值的则是复制链表。

    private static ComplexListNode ReconnectNodes(ComplexListNode head)
    {
        ComplexListNode node = head;
        ComplexListNode clonedHead = null;
        ComplexListNode clonedNode = null;

        if (node != null)
        {
            clonedHead = clonedNode = node.Next;
            node.Next = clonedNode.Next;
            node = node.Next;
        }

        while (node != null)
        {
            // 复制链表的连接
            clonedNode.Next = node.Next;
            clonedNode = clonedNode.Next;
            // 原始链表的连接
            node.Next = clonedNode.Next;
            node = node.Next;
        }

        return clonedHead;
    }

  最后,将三个步骤衔接起来形成Clone方法:

    public static ComplexListNode Clone(ComplexListNode head)
    {
        CloneNodes(head);
        ConnectSiblingNodes(head);
        return ReconnectNodes(head);
    }

三、单元测试

  辅助方法的封装

    public static void TestPortal(string testName, ComplexListNode head)
    {
        if (!string.IsNullOrEmpty(testName))
        {
            Console.WriteLine("{0} begins:", testName);
        }

        Console.WriteLine("The original list is:");
        PrintList(head);

        ComplexListNode clonedHead = Clone(head);
        Console.WriteLine("The cloned list is:");
        PrintList(clonedHead);
    }

    private static void PrintList(ComplexListNode head)
    {
        ComplexListNode node = head;
        while (node != null)
        {
            Console.WriteLine("The value of this node is: {0}.", node.Data);
            if (node.Sibling != null)
            {
                Console.WriteLine("The value of its sibling is: {0}.", node.Sibling.Data);
            }
            else
            {
                Console.WriteLine("This node does not have a sibling.");
            }

            Console.WriteLine();

            node = node.Next;
        }
    }

    private static void BuildNodes(ComplexListNode node, ComplexListNode next, ComplexListNode sibling)
    {
        if (node != null)
        {
            node.Next = next;
            node.Sibling = sibling;
        }
    }

  (1)Test1

    //          -----------------
    //         \|/              |
    //  1-------2-------3-------4-------5
    //  |       |      /|\             /|\
    //  --------+--------               |
    //          -------------------------
    public static void Test1()
    {
        ComplexListNode node1 = new ComplexListNode(1);
        ComplexListNode node2 = new ComplexListNode(2);
        ComplexListNode node3 = new ComplexListNode(3);
        ComplexListNode node4 = new ComplexListNode(4);
        ComplexListNode node5 = new ComplexListNode(5);

        BuildNodes(node1, node2, node3);
        BuildNodes(node2, node3, node5);
        BuildNodes(node3, node4, null);
        BuildNodes(node4, node5, node2);

        TestPortal("Test1", node1);
    }

  (2)Test2

    // Sibling指向结点自身
    //          -----------------
    //         \|/              |
    //  1-------2-------3-------4-------5
    //         |       | /|\           /|\
    //         |       | --             |
    //         |------------------------|
    public static void Test2()
    {
        ComplexListNode node1 = new ComplexListNode(1);
        ComplexListNode node2 = new ComplexListNode(2);
        ComplexListNode node3 = new ComplexListNode(3);
        ComplexListNode node4 = new ComplexListNode(4);
        ComplexListNode node5 = new ComplexListNode(5);

        BuildNodes(node1, node2, null);
        BuildNodes(node2, node3, node5);
        BuildNodes(node3, node4, node3);
        BuildNodes(node4, node5, node2);

        TestPortal("Test2", node1);
    }

  (3)Test3

    // Sibling形成环
    //          -----------------
    //         \|/              |
    //  1-------2-------3-------4-------5
    //          |              /|\
    //          |               |
    //          |---------------|
    public static void Test3()
    {
        ComplexListNode node1 = new ComplexListNode(1);
        ComplexListNode node2 = new ComplexListNode(2);
        ComplexListNode node3 = new ComplexListNode(3);
        ComplexListNode node4 = new ComplexListNode(4);
        ComplexListNode node5 = new ComplexListNode(5);

        BuildNodes(node1, node2, null);
        BuildNodes(node2, node3, node4);
        BuildNodes(node3, node4, null);
        BuildNodes(node4, node5, node2);

        TestPortal("Test3", node1);
    }

  (4)Test4

    // 只有一个结点
    public static void Test4()
    {
        ComplexListNode node1 = new ComplexListNode(1);
        node1.Sibling = node1;

        TestPortal("Test4", node1);
    }

  (5)Test5

    // 鲁棒性测试
    public static void Test5()
    {
        TestPortal("Test5", null);
    }

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

2496
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十九】Iterator&fail-fast机制

【Java提高十九】Iterator&fail-fast机制 Iterator详解 迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行...

40211
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

2256
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

2198
来自专栏chenssy

【死磕Java并发】-----J.U.C之阻塞队列:PriorityBlockingQueue

我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的...

3494
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

25310
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

5913
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

21810
来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

1293
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

32012

扫码关注云+社区

领取腾讯云代金券