题目:请实现函数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的指针没有画出。
第一步是复制原始链表上的每一个结点,并用Next节点链接起来;
第二步是设置每个结点的Sibling节点指针。
对于一个含有n个结点的链表,由于定位每个结点的Sibling都需要从链表头结点开始经过O(n)步才能找到,因此这种方法的总时间复杂度是O(n2)。
第一步仍然是复制原始链表上的每个结点N创建N',然后把这些创建出来的结点用Next链接起来。同时我们把<N,N'>的配对信息放到一个哈希表中。
第二步还是设置复制链表上每个结点的m_pSibling。由于有了哈希表,我们可以用O(1)的时间根据S找到S'。
此方法使用空间换时间。对于有n个结点的链表我们需要一个大小为O(n)的哈希表,也就是说我们以O(n)的空间消耗把时间复杂度由O(n2)降低到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
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。