LinkedList为什么我们必须在这里创建假人

Question

我是解决与数据结构相关的算法的新手，我不确定我遇到的问题的以下代码：

public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null && head.next.next != null) {
ListNode n1 = head.next, n2 = head.next.next;
head.next = n2;
n1.next = n2.next;
n2.next = n1;                   
head = n1;
}
return dummy.next;
}

为什么我们必须在这里创建假人？

如果你能在这件事上帮我，那将是一个很大的帮助。当你必须对链表执行一些操作时，我观察到了类似的步骤。

Answer 1

如果要交换链表中的两个节点，则需要更改这些节点中的next指针和前一个节点。

例如，您有一个列表A->B->C，并且要交换B和C，您需要更改所有节点中的next指针。

但是，如果要交换第一个两个节点，则需要更改这两个节点中的next指针和指向列表头的指针。

所以，你必须做的事情取决于你是否在列表的开头交换。。。但是函数的作者很懒，他不想写两种不同的交换代码。

Mr。因此，懒惰的程序员在必须交换所有东西之前就陷入了一个虚拟节点。这样一来，他一开始就不必交换任何东西，而且所有交换都可以使用相同的代码。他在最后删除了这个节点，这样就不会造成任何伤害。

在Java中创建一个虚拟节点并没有那么昂贵，但我不会这样做。

我会这样写两种方式：

public ListNode swapPairs(ListNode head) {

if (head != null && head.next != null) {
//swap first 2 nodes
ListNode n1 = head;
ListNode n2 = n1.next;
head = n2;
n1.next = n2.next;
n2.next = n1;                   
ListNode pred = n1;
//swap remainder
while (pred.next != null && pred.next.next != null) {
n1 = pred.next;
n2 = n1.next;
pred.next = n2;
n1.next = n2.next;
n2.next = n1;                   
pred = n1;
}
}
return head;
}

Answer 2

根本不需要添加虚拟节点。事实上，您通过添加虚拟节点作为头来更改链表的头。您的代码应该在没有伪节点的情况下工作。

public void swapPairs(ListNode head) {
if(head!=null) {
while (head.next != null && head.next.next != null) {
ListNode n1 = head.next, n2 = head.next.next;
head.next = n2;
n1.next = n2.next;
n2.next = n1;
head = n1;
}
}
}