java - 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 指针。

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

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

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

在 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;
}