題目描述
- 題目描述：復(fù)制一個復(fù)雜鏈表估脆，在復(fù)雜鏈表中钦奋，每個節(jié)點除了有一個next指針指向下一個節(jié)點，還有一個sibling指針指向鏈表中的任意節(jié)點或者null疙赠。
解題思路：
- 原始鏈表為：A(C)->B(E)->C(null)->D(B)->E(null)
- 復(fù)制原始鏈表節(jié)點N付材，創(chuàng)建N'，并將N'鏈接到N的后邊圃阳， 鏈表變?yōu)椋篈(C)->A'(null)>B(E)->B'(null)->C(null)->C'(null)->D(B)->D'(null)->E(null)->E'(null)
- 設(shè)置復(fù)制節(jié)點N'的sibling厌衔。鏈表變?yōu)椋篈(C)->A'(C')>B(E)->B'(E')->C(null)->C'(null)->D(B)->D'(B')->E(null)->E'(null)
- 把這個長鏈表拆分為兩個鏈表，獲取拷貝后的鏈表捍岳。
代碼
// 節(jié)點結(jié)構(gòu)
class ListNode {
String value;
ListNode next;
ListNode sibling;
public ListNode(String val) {
this.value = val;
}
}
ListNode deepCopy(ListNode root){
if (root == null) {
return null;
}
// 1. 復(fù)制鏈表富寿，插入原始鏈表節(jié)點之后
ListNode tempNode = root;
while (tempNode != null) {
ListNode newNode = new ListNode(tempNode.value);
newNode.next = tempNode.next;
tempNode.next = newNode;
tempNode = newNode.next;
}
// 2. 設(shè)置sibling
tempNode = root;
while (tempNode != null) {
if (tempNode.sibling!= null) {
tempNode.next.sibling = tempNode.sibling.next;
}
tempNode = tempNode.next.next;
}
// 3. 把這個長鏈表拆分為兩個鏈表
tempNode = root;
ListNode copyedHead = null;
ListNode copyedNode = null;
if (tempNode != null) {
// 設(shè)置復(fù)制鏈表的頭節(jié)點
copyedHead = tempNode.next;
copyedNode = copyedHead;
tempNode.next = copyedNode.next;
tempNode = tempNode.next;
}
while (tempNode != null) {
copyedNode.next = tempNode.next;
copyedNode = copyedNode.next;
tempNode.next = copyedNode.next;
tempNode = tempNode.next;
}
return copyedHead;
}
