原创

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

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

 

正文到此结束
本文目录