JZ-C-37

剑指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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
//============================================================================
// Name        : JZ-C-37.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 两个链表的第一个公共结点
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include "List.h"
using namespace std;
 
unsigned int GetListLength(ListNode* pHead);
/**
 * 先移动长链表指针至某位置(与短链表持平),再同时遍历,遇到第一个相同的结点即为公共结点
 * 时间复杂度为O(m+n)
 */
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) {
    // 得到两个链表的长度
    unsigned int nLength1 = GetListLength(pHead1);
    unsigned int nLength2 = GetListLength(pHead2);
    int nLengthDif = nLength1 - nLength2;
 
    ListNode* pListHeadLong = pHead1;
    ListNode* pListHeadShort = pHead2;
    if (nLength2 > nLength1) {
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
        nLengthDif = nLength2 - nLength1;
    }
 
    // 先在长链表上走几步,再同时在两个链表上遍历
    for (int i = 0; i < nLengthDif; ++i)
        pListHeadLong = pListHeadLong->m_pNext;
 
    while ((pListHeadLong != NULL) && (pListHeadShort != NULL)
            && (pListHeadLong != pListHeadShort)) {
        pListHeadLong = pListHeadLong->m_pNext;//当不存在公共结点时,返回NULL
        pListHeadShort = pListHeadShort->m_pNext;
    }
 
    // 得到第一个公共结点
    ListNode* pFisrtCommonNode = pListHeadLong;
 
    return pFisrtCommonNode;
}
 
unsigned int GetListLength(ListNode* pHead) {
    unsigned int nLength = 0;
    ListNode* pNode = pHead;
    while (pNode != NULL) {
        ++nLength;
        pNode = pNode->m_pNext;
    }
 
    return nLength;
}
 
// ====================测试代码====================
void DestroyNode(ListNode* pNode);
 
void Test(char* testName, ListNode* pHead1, ListNode* pHead2,
        ListNode* pExpected) {
    if (testName != NULL)
        printf("%s begins: ", testName);
 
    ListNode* pResult = FindFirstCommonNode(pHead1, pHead2);
    if (pResult == pExpected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}
 
// 第一个公共结点在链表中间
// 1 - 2 - 3 \
//            6 - 7
//     4 - 5 /
void Test1() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
    ListNode* pNode6 = CreateListNode(6);
    ListNode* pNode7 = CreateListNode(7);
 
    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode6);
    ConnectListNodes(pNode4, pNode5);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);
 
    Test("Test1", pNode1, pNode4, pNode6);
 
    DestroyNode(pNode1);
    DestroyNode(pNode2);
    DestroyNode(pNode3);
    DestroyNode(pNode4);
    DestroyNode(pNode5);
    DestroyNode(pNode6);
    DestroyNode(pNode7);
}
 
// 没有公共结点
// 1 - 2 - 3 - 4
//
// 5 - 6 - 7
void Test2() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
    ListNode* pNode6 = CreateListNode(6);
    ListNode* pNode7 = CreateListNode(7);
 
    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);
 
    Test("Test2", pNode1, pNode5, NULL);
 
    DestroyList(pNode1);
    DestroyList(pNode5);
}
 
// 公共结点是最后一个结点
// 1 - 2 - 3 - 4 \
//                7
//         5 - 6 /
void Test3() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
    ListNode* pNode6 = CreateListNode(6);
    ListNode* pNode7 = CreateListNode(7);
 
    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode7);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);
 
    Test("Test3", pNode1, pNode5, pNode7);
 
    DestroyNode(pNode1);
    DestroyNode(pNode2);
    DestroyNode(pNode3);
    DestroyNode(pNode4);
    DestroyNode(pNode5);
    DestroyNode(pNode6);
    DestroyNode(pNode7);
}
 
// 公共结点是第一个结点
// 1 - 2 - 3 - 4 - 5
// 两个链表完全重合
void Test4() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
 
    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
 
    Test("Test4", pNode1, pNode1, pNode1);
 
    DestroyList(pNode1);
}
 
// 输入的两个链表有一个空链表
void Test5() {
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
 
    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
 
    Test("Test5", NULL, pNode1, NULL);
 
    DestroyList(pNode1);
}
 
// 输入的两个链表有一个空链表
void Test6() {
    Test("Test6", NULL, NULL, NULL);
}
 
void DestroyNode(ListNode* pNode) {
    delete pNode;
    pNode = NULL;
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
 
    return 0;
}

发表评论

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