我正在用 java 練習(xí)鏈表編程問(wèn)題，我有以下問(wèn)題的有效解決方案，但無(wú)法理解它是如何工作的。我在每一行旁邊都評(píng)論了我認(rèn)為應(yīng)該發(fā)生的事情，但顯然我還沒(méi)有理解這些是如何工作的，有人可以解釋我的評(píng)論在哪里錯(cuò)誤以及這個(gè)解決方案是如何正確的。（在我的評(píng)論中，我使用 h 作為頭部, s 表示慢等）給定一個(gè)鏈表，交換每?jī)蓚€(gè)相鄰節(jié)點(diǎn)并返回其頭部。示例：給定 1->2->3->4，您應(yīng)該將列表返回為 2->1->4->3。public Node s(Node head) { // 1(h)-2-3-4 passed in // if only 1 node or null node return it if (head == null || head.next == null) { return head; } Node slow = head.next; // 1h-2s-3-4 head.next = head.next.next; // 1h-3-4 slow.next = head; // 2s-1h-3-4 head = slow; // 2s/h-1-3-4 Node parent = slow.next; // 1p-3-4 slow = slow.next.next; // 3s-4 while (slow != null && slow.next != null) { Node temp = slow.next; // 4t-null slow.next = slow.next.next; // 3s-null temp.next = slow; // 4t-3s-null parent.next = temp; // 1p-4-3 parent = parent.next.next; // 3p=null slow = slow.next; // 4-null, loop ends cause next to slow is null } return head; // ( head = slow from earlier) 4-null }
3 回答
至尊寶的傳說(shuō)
TA貢獻(xiàn)1789條經(jīng)驗(yàn) 獲得超10個(gè)贊
讓我們假設(shè)一個(gè)鏈表A -> B -> C -> D。
我已經(jīng)對(duì)您的代碼中的行進(jìn)行了編號(hào)，以便于討論。
1 public Node s(Node head) {
2 // if only 1 node or null node return it
3 if (head == null || head.next == null) {
4 return head;
5 }
6
7 Node slow = head.next;
8 head.next = head.next.next;
9 slow.next = head;
10 head = slow;
11 Node parent = slow.next;
12 slow = slow.next.next;
13
14 while (slow != null && slow.next != null) {
15 Node temp = slow.next;
16 slow.next = slow.next.next;
17 temp.next = slow;
18 parent.next = temp;
19 parent = parent.next.next;
20 slow = slow.next;
21 }
22 return head;
23 }
在第 7 行，slow指向節(jié)點(diǎn) B。head.next在第 8 行設(shè)置為 B 的后繼者，C。在第 9 行，B 指向 A，在第 10 行，head指向 B。我的評(píng)論表明發(fā)生了什么。
7 Node slow = head.next; // slow = B
8 head.next = head.next.next; // head.next = C
9 slow.next = head; // B.next = A (because head points to A)
10 head = slow; // head = B
該代碼交換了前兩個(gè)節(jié)點(diǎn)。您的列表現(xiàn)在如下所示：
B -> A -> C -> D
現(xiàn)在代碼有點(diǎn)混亂，主要是由于命名不當(dāng)。slow當(dāng)前指向 B。
11 Node parent = slow.next; // parent = A
12 slow = slow.next.next; // slow = C
請(qǐng)記住，slow現(xiàn)在指向 C。這是接下來(lái)發(fā)生的事情：
14 while (slow != null && slow.next != null) {
15 Node temp = slow.next; // temp = D
16 slow.next = slow.next.next; // C.next = D.next (which is null)
17 temp.next = slow; // D.next = C
18 parent.next = temp; // A.next = D
此時(shí)，節(jié)點(diǎn) C 和 D 已交換，并且 A 指向 D，根據(jù)需要。該列表現(xiàn)在看起來(lái)像B -> A -> D -> C.
循環(huán)中的最后兩行只是為下次設(shè)置。請(qǐng)記住，現(xiàn)在parent指向 A。
19 parent = parent.next.next; // parent = C
20 slow = slow.next; // slow = null
循環(huán)回到頂部，我們看到slow == null，所以循環(huán)退出。
雖然您發(fā)布的代碼有效，但它不必要地令人困惑。在進(jìn)入循環(huán)之前不需要對(duì)前兩個(gè)節(jié)點(diǎn)進(jìn)行特殊交換，并且變量名稱可以更具描述性。
要交換兩個(gè)節(jié)點(diǎn)，您必須將第二個(gè)點(diǎn)指向第一個(gè)，并將第一個(gè)指向第二個(gè)的后繼節(jié)點(diǎn)。為此，您必須在覆蓋它之前保存第二個(gè)的繼任者。例如，如果你有A -> B -> C并且你想要B -> A -> C，那么你必須這樣做，假設(shè)head指向 A：
firstNode = head // firstNode points to A
secondNode = firstNode.next // secondNode points to B
secondNodeSuccessor = secondNode.next // this points to C
secondNode.next = firstNode // B now points to A
firstNode.next = secondNodeSuccessor // A now points to C
head = secondNode // and head points to B
此時(shí)，secondNodeSuccessor指向C，即下一個(gè)firstNode。
了解如何交換節(jié)點(diǎn)后，您可以大大簡(jiǎn)化代碼：
public Node s(Node head) {
// if fewer than 2 nodes, return.
if (head == null || head == null) {
return head;
}
// we know that the new head will be the second node.
Node firstNode = head;
Node parentNode = null;
while (firstNode != null && firstNode.next != null) {
Node secondNode = firstNode.next;
Node secondNodeSuccessor = secondNode.next;
// swap the nodes
secondNode.next = firstNode;
firstNode.next = secondNodeSuccessor;
if (parentNode != null) {
// This links the previous node (the one right before
// the two that we just swapped) to the swapped nodes.
parentNode.next = secondNode;
}
// the new parent node is the last swapped node.
parentNode = firstNode;
firstNode = firstNode.next; // set up for next pair
}
return head.next;
}
注意這里的改進(jìn)：
我消除了前兩個(gè)節(jié)點(diǎn)的特殊情況交換，這通過(guò)使每個(gè)交換相同來(lái)簡(jiǎn)化事情。
有意義的變量名稱使我所引用的節(jié)點(diǎn)一目了然。
消除.next.next構(gòu)造可以更容易地對(duì)代碼進(jìn)行推理，并且還可以更輕松地確定代碼是否有可能取消對(duì) null 的引用。
您的調(diào)試器是一個(gè)非常有用的工具，可以幫助您了解代碼的工作方式。如果您要在調(diào)試器中單步執(zhí)行代碼，您可以檢查變量并查看每行代碼如何影響狀態(tài)。如果您不知道如何使用您的調(diào)試器，您現(xiàn)在應(yīng)該花時(shí)間學(xué)習(xí)。它將為您節(jié)省數(shù)小時(shí)的調(diào)試時(shí)間，并極大地增加您對(duì)代碼工作方式的理解。
白板的微信
TA貢獻(xiàn)1883條經(jīng)驗(yàn) 獲得超3個(gè)贊
代替交換節(jié)點(diǎn)，我們可以只交換數(shù)據(jù)，這很容易并且會(huì)得到所需的輸出。
public Node s(Node head) {
if (head == null || head.next == null) {
return head;
}
Node temp = head;
/* Traverse only till there are atleast 2 nodes left */
while (temp != null && temp.next != null) {
/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
return head;
}
嗶嗶one
TA貢獻(xiàn)1854條經(jīng)驗(yàn) 獲得超8個(gè)贊
其他兩種解決方案要么不符合您的要求，要么為某些輸入提供錯(cuò)誤的結(jié)果。
我提出了一個(gè)我在LeetCode 上測(cè)試過(guò)的替代方法（如果你想自己測(cè)試，請(qǐng)務(wù)必將 Node 類型重命名為 ListNode）。我希望我添加到代碼中的注釋足夠清楚。如有疑問(wèn)，我建議嘗試在交互式調(diào)試器中執(zhí)行此過(guò)程。
public ListNode s(Node head) {
// if the list is empty or it's a singleton, no node needs to be swapped
if (head == null || head.next == null) {
return head;
}
// first and second are the first and second node of the current pair to swap
Node first = head;
Node second = head.next;
// parent is the node immediately before the current pair.
// Initially, there is no such pair
Node parent = null;
// the updated list starts from the second node of the first pair
head = second;
// iterate until there is a valid pair to swap
while (first != null && second != null) {
// swap the two nodes of the current pair
first.next = second.next;
second.next = first;
if (parent != null) {
// attach the second element to the updated node of the previous pair
parent.next = second;
}
// keep the invariant of parent valid: parent precedes the new pair to swap,
// if such a pair exists
parent = first;
// advance the pointers of the first and second elements of the new pair to swap
first = first.next;
second = (first == null) ? null : first.next;
}
return head;
}
添加回答
舉報(bào)
0/150
提交
取消