Давайте предположим, что связанный список A -> B -> C -> D.
Я пронумеровал строки в вашем коде, чтобы было легче говорить.
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 указывает на узел B. head.next устанавливается на преемника B, C в строке 8. В строке 9 B указывает на A, а в строке 10 head указывает на B. Мои комментарии показывают, что произошло.
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
Этот код поменял местами первые два узла.Ваш список теперь выглядит следующим образом:
B -> A -> C -> D
Теперь код становится немного запутанным, в основном из-за плохого именования.slow в настоящее время указывает на B.
11 Node parent = slow.next; // parent = A
12 slow = slow.next.next; // slow = C
Помните, что slow теперь указывает на C. Вот что происходит дальше:
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
На этом этапе узлы C и D имеютпоменялся местами, и А указывает на D, как требуется.Теперь список выглядит так: B -> A -> D -> C.
Последние две строки в цикле просто настраивают на следующий раз.Помните, что прямо сейчас parent указывает на A.
19 parent = parent.next.next; // parent = C
20 slow = slow.next; // slow = null
Возвращаясь к вершине, мы видим, что slow == null, поэтому цикл завершается.
В то время как код выразмещенные работы, это излишне запутанно.Нет необходимости делать специальный обмен первыми двумя узлами перед входом в цикл, а имена переменных могут быть более наглядными.
Чтобы поменять местами два узла, необходимо сделать вторую точку на первом, ипервая точка на второй преемник.Чтобы сделать это, вы должны сохранить преемника второго, прежде чем перезаписать его.Например, если у вас есть A -> B -> C и вы хотите B -> A -> C, то вы должны сделать это, предполагая, что 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
В этот момент, secondNodeSuccessor указываетк C, который является следующим firstNode.
С этим пониманием того, как поменять узлы, вы можете немного упростить код:
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;
}
Обратите внимание на улучшения здесь:
- Я исключил особый случай замены первых двух узлов, что упрощает процесс, делая каждый обмен одинаковым.
- Значимые имена переменных позволяют понять, на какой узел я ссылаюсь.
- Исключение конструкции
.next.next упрощает анализ кода, а также помогает определить, может ли код потенциально разыменовать нуль.
Ваш отладчикочень полезный инструмент для понимания того, как работает ваш код.Если бы вы пошагово выполняли код в своем отладчике, вы могли бы изучить переменные и посмотреть, как каждая строка кода влияет на состояние.Если вы не знаете, как использовать отладчик, вам стоит потратить время на изучение.Это сэкономит вам часов отладки, а также значительно улучшит ваше понимание того, как работает код.