纵有疾风起
人生不言弃

剑指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的指针没有画出。

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

二、解题思路

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的后面)

剑指Offer面试题:24.复杂链表的复制插图(1)

    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)

剑指Offer面试题:24.复杂链表的复制插图(2)

    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链接起来就是原始链表,偶数数值的则是复制链表。

剑指Offer面试题:24.复杂链表的复制插图(3)

    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);    }

三、单元测试

  辅助方法的封装

剑指Offer面试题:24.复杂链表的复制插图(4)

    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;        }    }

View Code

  (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);    }

剑指Offer面试题:24.复杂链表的复制插图(6)

  (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);    }

剑指Offer面试题:24.复杂链表的复制插图(7)

  (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);    }

剑指Offer面试题:24.复杂链表的复制插图(8)

  (4)Test4

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

剑指Offer面试题:24.复杂链表的复制插图(9)

  (5)Test5

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

剑指Offer面试题:24.复杂链表的复制插图(10)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4790090.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:24.复杂链表的复制

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活