题目：请实现ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibing指向链表中的任意结点或者null。
struct ComplexListNode{
int m_nValue;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
}
分析思路：
第一步是根据原始链表的每个结点N创建对应的N'，但是是把N'链接在N的后面。
第二步是设置复制出来的结点的m_pSibling。假设原始链表上的N的m_pSibling指向结点S，那么其对应复制出来的N'是N的m_pNext指向的结点，同样S'也是S的m_pNext指向的结点。
第三步是把这个长链表拆分成两个链表：把奇数位置的结点用m_pNext链接起来就是原始链表，把偶数位置的结点用m_pNext链接起来就是复制出来的链表。
测试用例：
1）功能测试（包括结点中的m_pSibling指向结点自身，两个结点的m_pSibling形成环状结构，链表中只有一个结点）；
2）特殊输入测试（指向链表头结点的指针为null指针）。
代码实现：
package com.yyq; /** * Created by Administrator on 2015/9/20. */ public class CopyComplexList { //第一步：复制每个结点 public static void cloneNodes(ComplexListNode pHead){ ComplexListNode pNode = pHead; while(pNode != null){ ComplexListNode pCloned = new ComplexListNode(); pCloned.setM_nValue(pNode.getM_nValue()); pCloned.setM_pNext(pNode.getM_pNext()); pNode.setM_pNext(pCloned); pNode = pCloned.getM_pNext(); } } //第二步：复制m_pSibling结点 public static void connectSiblingNodes(ComplexListNode pHead){ ComplexListNode pNode = pHead; while (pNode != null){ ComplexListNode pCloned = pNode.getM_pNext(); if (pNode.getM_pSibling() != null){ pCloned.setM_pSibling(pNode.getM_pSibling().getM_pNext()); } pNode = pCloned.getM_pNext(); } } //第三步：将这个长链表分成两个表 public static ComplexListNode reconnectNodes(ComplexListNode pHead){ ComplexListNode pNode = pHead; ComplexListNode pClonedHead = null; ComplexListNode pClonedNode = null; if (pNode != null){ pClonedHead = pNode.getM_pNext(); pClonedNode = pNode.getM_pNext(); pNode.setM_pNext(pClonedNode.getM_pNext()); pNode = pNode.getM_pNext(); } while(pNode != null){ pClonedNode.setM_pNext(pNode.getM_pNext()); pClonedNode = pClonedNode.getM_pNext(); pNode.setM_pNext(pClonedNode.getM_pNext()); pNode = pNode.getM_pNext(); } return pClonedHead; } public static ComplexListNode clone(ComplexListNode pHead){ cloneNodes(pHead); connectSiblingNodes(pHead); return reconnectNodes(pHead); } // ====================测试代码==================== public static void Test(String testName, ComplexListNode pHead) { if(testName != null) System.out.println(testName + " begins:"); System.out.println("The original list is:"); ComplexListNode pNode = new ComplexListNode(); pNode.printListNode(pHead); ComplexListNode pClonedHead = clone(pHead); System.out.println("The cloned list is:"); pNode.printListNode(pClonedHead); } // ----------------- // |/ | // 1-------2-------3-------4-------5 // | | /| /| // --------+-------- | // ------------------------- public static void Test1() { ComplexListNode pNode1 = new ComplexListNode(1); ComplexListNode pNode2 = new ComplexListNode(2); ComplexListNode pNode3 = new ComplexListNode(3); ComplexListNode pNode4 = new ComplexListNode(4); ComplexListNode pNode5 = new ComplexListNode(5); pNode1.buildNodes(pNode2, pNode3); pNode2.buildNodes(pNode3, pNode5); pNode3.buildNodes(pNode4, null); pNode4.buildNodes(pNode5, pNode2); Test("Test1", pNode1); } // m_pSibling指向结点自身 // ----------------- // |/ | // 1-------2-------3-------4-------5 // | | /| /| // | | -- | // |------------------------| public static void Test2() { ComplexListNode pNode1 = new ComplexListNode(1); ComplexListNode pNode2 = new ComplexListNode(2); ComplexListNode pNode3 = new ComplexListNode(3); ComplexListNode pNode4 = new ComplexListNode(4); ComplexListNode pNode5 = new ComplexListNode(5); pNode1.buildNodes(pNode2, null); pNode2.buildNodes(pNode3, pNode5); pNode3.buildNodes(pNode4, pNode3); pNode4.buildNodes(pNode5, pNode2); Test("Test2", pNode1); } // m_pSibling形成环 // ----------------- // |/ | // 1-------2-------3-------4-------5 // | /| // | | // |---------------| public static void Test3() { ComplexListNode pNode1 = new ComplexListNode(1); ComplexListNode pNode2 = new ComplexListNode(2); ComplexListNode pNode3 = new ComplexListNode(3); ComplexListNode pNode4 = new ComplexListNode(4); ComplexListNode pNode5 = new ComplexListNode(5); pNode1.buildNodes(pNode2, null); pNode2.buildNodes(pNode3, pNode4); pNode3.buildNodes(pNode4, null); pNode4.buildNodes(pNode5, pNode2); Test("Test3", pNode1); } // 只有一个结点 public static void Test4() { ComplexListNode pNode1 = new ComplexListNode(1); pNode1.buildNodes(null, pNode1); Test("Test4", pNode1); } // 鲁棒性测试 public static void Test5() { Test("Test5", null); } public static void main(String[] args) { Test1(); Test2(); Test3(); Test4(); Test5(); } }
结果输出：
Test1 begins:
The original list is:
The value of this node is: 1
The value of its sibling is: 3
The value of this node is: 2
The value of its sibling is: 5
The value of this node is: 3
This node does not have a sibling.
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
The cloned list is:
The value of this node is: 1
The value of its sibling is: 3
The value of this node is: 2
The value of its sibling is: 5
The value of this node is: 3
This node does not have a sibling.
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
Test2 begins:
The original list is:
The value of this node is: 1
This node does not have a sibling.
The value of this node is: 2
The value of its sibling is: 5
The value of this node is: 3
The value of its sibling is: 3
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
The cloned list is:
The value of this node is: 1
This node does not have a sibling.
The value of this node is: 2
The value of its sibling is: 5
The value of this node is: 3
The value of its sibling is: 3
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
Test3 begins:
The original list is:
The value of this node is: 1
This node does not have a sibling.
The value of this node is: 2
The value of its sibling is: 4
The value of this node is: 3
This node does not have a sibling.
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
The cloned list is:
The value of this node is: 1
This node does not have a sibling.
The value of this node is: 2
The value of its sibling is: 4
The value of this node is: 3
This node does not have a sibling.
The value of this node is: 4
The value of its sibling is: 2
The value of this node is: 5
This node does not have a sibling.
Test4 begins:
The original list is:
The value of this node is: 1
The value of its sibling is: 1
The cloned list is:
The value of this node is: 1
The value of its sibling is: 1
Test5 begins:
The original list is:
The cloned list is: