forked from Wang-Jun-Chao/coding-interviews
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Test26.java
235 lines (210 loc) · 7.21 KB
/
Test26.java
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
/**
* Author: 王俊超
* Date: 2015-04-24
* Time: 18:08
* Declaration: All Rights Reserved !!!
*/
public class Test26 {
/**
* 复杂链表结点
*/
public static class ComplexListNode {
int value;
ComplexListNode next;
ComplexListNode sibling;
}
/**
* 实现函复制一个复杂链表。在复杂链表中,每个结点除了有一个next字段指向下一个结点外,
* 还有一个sibling字段指向链表中的任意结点或者NULL
*
* @param head 链表表头结点
* @return 复制结点的头结点
*/
public static ComplexListNode clone(ComplexListNode head) {
// 如果链表为空就直接返回空
if (head == null) {
return null;
}
// 先复制结点
cloneNodes(head);
// 再链接sibling字段
connectNodes(head);
// 将整个链表拆分,返回复制链表的头结点
return reconnectNodes(head);
}
/**
* 复制一个链表,并且将复制后的结点插入到被复制的结点后面,只链接复制结点的next字段
*
* @param head 待复制链表的头结点
*/
public static void cloneNodes(ComplexListNode head) {
// 如果链表不空,进行复制操作
while (head != null) {
// 创建一个新的结点
ComplexListNode tmp = new ComplexListNode();
// 将被复制结点的值传给复制结点
// tmp.value = head.value;
///////////////////////////////////////////////////////////////////////////////////////////
// TODO 此处为了做测试,让复制结点的值都增加了100,如果不需要可以将下面一个行注释掉,打开上一行。
tmp.value = head.value + 100;
///////////////////////////////////////////////////////////////////////////////////////////
// 复制结点的next指向下一个要被复制的结点
tmp.next = head.next;
// 被复制结点的next指向复制结点
head.next = tmp;
// 到些处就已经完成了一个结点的复制并且插入到被复制结点的后面
// heed指向下一个被复制结点的位置
head = tmp.next;
}
}
/**
* 设置复制结点的sibling字段
*
* @param head 链表的头结
*/
public static void connectNodes(ComplexListNode head) {
// 如链表不为空
while (head != null) {
// 当前处理的结点sibling字段不为空,则要设置其复制结点的sibling字段
if (head.sibling != null) {
// 复制结点的sibling指向被复制结点的sibling字段的下一个结点
// head.next:表求复制结点,
// head.sibling:表示被复制结点的sibling所指向的结点,
// 它的下一个结点就是它的复制结点
head.next.sibling = head.sibling.next;
}
// 指向下一个要处理的复制结点
head = head.next.next;
}
}
/**
* 刚复制结点和被复制结点拆开,还原被复制的链表,同时生成监制链表
*
* @param head 链表的头结点
* @return 复制链表的头结点
*/
public static ComplexListNode reconnectNodes(ComplexListNode head) {
// 当链表为空就直接返回空
if (head == null) {
return null;
}
// 用于记录复制链表的头结点
ComplexListNode newHead = head.next;
// 用于记录当前处理的复制结点
ComplexListNode pointer = newHead;
// 被复制结点的next指向下一个被复制结点
head.next = newHead.next;
// 指向新的被复制结点
head = head.next;
while (head != null) {
// pointer指向复制结点
pointer.next = head.next;
pointer = pointer.next;
// head的下一个指向复制结点的下一个结点,即原来链表的结点
head.next = pointer.next;
// head指向下一个原来链表上的结点
head = pointer.next;
}
// 返回复制链表的头结点
return newHead;
}
/**
* 输出链表信息
*
* @param head 链表头结点
*/
public static void printList(ComplexListNode head) {
while (head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
/**
* 判断两个链表是否是同一个链表,不是值相同
*
* @param h1 链表头1
* @param h2 链表头2
* @return true:两个链表是同一个链表,false:不是
*/
public static boolean isSame(ComplexListNode h1, ComplexListNode h2) {
while (h1 != null && h2 != null) {
if (h1 == h2) {
h1 = h1.next;
h2 = h2.next;
} else {
return false;
}
}
return h1 == null && h2 == null;
}
public static void main(String[] args) {
// -----------------
// \|/ |
// 1-------2-------3-------4-------5
// | | /|\ /|\
// --------+-------- |
// -------------------------
ComplexListNode head = new ComplexListNode();
head.value = 1;
head.next = new ComplexListNode();
head.next.value = 2;
head.next.next = new ComplexListNode();
head.next.next.value = 3;
head.next.next.next = new ComplexListNode();
head.next.next.next.value = 4;
head.next.next.next.next = new ComplexListNode();
head.next.next.next.next.value = 5;
head.sibling = head.next.next;
head.next.sibling = head.next.next.next.next.next;
head.next.next.next.sibling = head.next;
ComplexListNode tmp = head;
printList(head);
ComplexListNode newHead = clone(head);
printList(head);
System.out.println(isSame(head, tmp));
printList(newHead);
System.out.println(isSame(head, newHead));
// 有指向自身的情况
// -----------------
// \|/ |
// 1-------2-------3-------4-------5
// | | /|\ /|\
// | | -- |
// |------------------------|
ComplexListNode head2 = new ComplexListNode();
head2.value = 1;
head2.next = new ComplexListNode();
head2.next.value = 2;
head2.next.next = new ComplexListNode();
head2.next.next.value = 3;
head2.next.next.next = new ComplexListNode();
head2.next.next.next.value = 4;
head2.next.next.next.next = new ComplexListNode();
head2.next.next.next.next.value = 5;
head2.next.sibling = head2.next.next.next.next;
head2.next.next.next.sibling = head2.next.sibling;
head2.next.next.sibling = head2.next.next;
System.out.println("\n");
tmp = head2;
printList(head2);
ComplexListNode newHead2 = clone(head2);
printList(head2);
System.out.println(isSame(head2, tmp));
printList(newHead2);
System.out.println(isSame(head2, newHead2));
ComplexListNode head3 = new ComplexListNode();
head3.value = 1;
System.out.println("\n");
tmp = head3;
printList(head3);
ComplexListNode newHead3 = clone(head3);
printList(head3);
System.out.println(isSame(head3, tmp));
printList(newHead3);
System.out.println(isSame(head3, newHead3));
System.out.println("\n");
ComplexListNode head4 = clone(null);
printList(head4);
}
}