JZ-C-26

剑指offer第二十六题:复杂链表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
//============================================================================
// Name        : JZ-C-26.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 复杂链表的复制
//============================================================================
 
#include <iostream>
#include "ComplexList.h"
#include <stdio.h>
using namespace std;
 
void CloneNodes(ComplexListNode* pHead);
void ConnectSiblingNodes(ComplexListNode* pHead);
ComplexListNode* ReconnectNodes(ComplexListNode* pHead);
 
ComplexListNode* Clone(ComplexListNode* pHead) {
    CloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}
/**
 *第一步:克隆Next结点
 */
void CloneNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    while (pNode != NULL) {
        ComplexListNode* pCloneNode = new ComplexListNode();
        pCloneNode->m_nValue = pNode->m_nValue;
        pCloneNode->m_pNext = pNode->m_pNext;
        pNode->m_pNext = pCloneNode;
        pNode = pCloneNode->m_pNext; //进行下一次Clone
    }
}
/**
 *第二步:连接Sibling结点
 */
void ConnectSiblingNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    while (pNode != NULL) {
        ComplexListNode* pCloneNode = pNode->m_pNext;
        if (pNode->m_pSibling != NULL) {
            pCloneNode->m_pSibling = pNode->m_pSibling->m_pNext;
        }
        pNode = pCloneNode->m_pNext;
    }
}
/**
 *第三步:拆分出复制的复杂链表
 */
ComplexListNode* ReconnectNodes(ComplexListNode* pHead) {
    ComplexListNode* pNode = pHead;
    ComplexListNode* pCloneHead = NULL;
    ComplexListNode* pCloneNode = NULL;
    if (pNode != NULL) {
        pCloneHead = pCloneNode = pNode->m_pNext; //先确定复制链表的头
        pNode = pCloneNode->m_pNext;
    }
    while (pNode != NULL) {
        pCloneNode->m_pNext = pNode->m_pNext;
        pCloneNode = pCloneNode->m_pNext;
        pNode = pCloneNode->m_pNext;
    }
    return pCloneHead;
}
 
// ====================测试代码====================
void Test(char* testName, ComplexListNode* pHead) {
    if (testName != NULL)
        printf("%s begins:\n", testName);
 
    printf("The original list is:\n");
    PrintList(pHead);
 
    ComplexListNode* pClonedHead = Clone(pHead);
 
    printf("The cloned list is:\n");
    PrintList(pClonedHead);
}
 
//          -----------------
//         \|/              |
//  1-------2-------3-------4-------5
//  |       |      /|\             /|\
//  --------+--------               |
//          -------------------------
void Test1() {
    ComplexListNode* pNode1 = CreateNode(1);
    ComplexListNode* pNode2 = CreateNode(2);
    ComplexListNode* pNode3 = CreateNode(3);
    ComplexListNode* pNode4 = CreateNode(4);
    ComplexListNode* pNode5 = CreateNode(5);
 
    BuildNodes(pNode1, pNode2, pNode3);
    BuildNodes(pNode2, pNode3, pNode5);
    BuildNodes(pNode3, pNode4, NULL);
    BuildNodes(pNode4, pNode5, pNode2);
 
    Test("Test1", pNode1);
}
 
// m_pSibling指向结点自身
//          -----------------
//         \|/              |
//  1-------2-------3-------4-------5
//         |       | /|\           /|\
//         |       | --             |
//         |------------------------|
void Test2() {
    ComplexListNode* pNode1 = CreateNode(1);
    ComplexListNode* pNode2 = CreateNode(2);
    ComplexListNode* pNode3 = CreateNode(3);
    ComplexListNode* pNode4 = CreateNode(4);
    ComplexListNode* pNode5 = CreateNode(5);
 
    BuildNodes(pNode1, pNode2, NULL);
    BuildNodes(pNode2, pNode3, pNode5);
    BuildNodes(pNode3, pNode4, pNode3);
    BuildNodes(pNode4, pNode5, pNode2);
 
    Test("Test2", pNode1);
}
 
// m_pSibling形成环
//          -----------------
//         \|/              |
//  1-------2-------3-------4-------5
//          |              /|\
//          |               |
//          |---------------|
void Test3() {
    ComplexListNode* pNode1 = CreateNode(1);
    ComplexListNode* pNode2 = CreateNode(2);
    ComplexListNode* pNode3 = CreateNode(3);
    ComplexListNode* pNode4 = CreateNode(4);
    ComplexListNode* pNode5 = CreateNode(5);
 
    BuildNodes(pNode1, pNode2, NULL);
    BuildNodes(pNode2, pNode3, pNode4);
    BuildNodes(pNode3, pNode4, NULL);
    BuildNodes(pNode4, pNode5, pNode2);
 
    Test("Test3", pNode1);
}
 
// 只有一个结点
void Test4() {
    ComplexListNode* pNode1 = CreateNode(1);
    BuildNodes(pNode1, NULL, pNode1);
 
    Test("Test4", pNode1);
}
 
// 鲁棒性测试
void Test5() {
    Test("Test5", NULL);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注