24. 两两交换链表中的节点

• 本文主要讲述自己做题中 debug 的过程，以及三点关于题目的理解

几点关于这道题的理解

1. 理解第三步的指向

   • 

     转自 代码随想录

   • 步骤三的意义是什么呢？
     • 其意义是判断下一次还是否要进行结点交换
     • 可以看见在示例（1-2-3-4）里，它是指向 3 而不是 4。如果 3 的这个位置是 null，我们就不进行下一步交换了
   • 至于为什么步骤三是指向 3 而不是 4 ？
     • 这是因为我们下一步会重设 cur ，然后在新的循环里，让 cur ·指向 4 再指向 3，然后指向 null

2. cur 的重设位置一定要对

   • 代码位置为 line21 cur = cur.next.next;
   • 执行完步骤三，我们是先重新设置 cur ，再进行 while 的条件判断。这里 cur 一定设置对，不然后续循环会乱。

3. 为什么最后返回自己设定的 虚拟头结点的下一个结点，而不是 head？

   • head 和 dummyNode 都是头结点，各自连接一条链表。
   • dummyNode 连接的链表经过我们 cur 重新设定了后续结点的 next 关系 。
   • 而 head 连接的链表，我们并没有改变其后续结点的 next 关系
   • 所以我们想返回已修改过的链表，得返回 dummyNode.next。

答案

class Solution
{
    public ListNode swapPairs(ListNode head)
    {
        //虚拟头节点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        //重设一个头节点指向 dummyNode ，方便后续返回头节点 dummyNode.next
        ListNode cur = dummyNode;

        //进行三步骤交换
        while (cur.next != null && cur.next.next != null)
        {
            //保存 cur.next; 和 cur.next.next.next;
            ListNode temp1 = cur.next;
            ListNode temp2 = cur.next.next.next;
            cur.next = cur.next.next; //第一步
            cur.next.next = temp1; //第二步
            cur.next.next.next = temp2; //第三步
            cur = cur.next.next; //重设 cur
        }
        //返回自己设定的 虚拟头结点的下一个结点，而不是 head
        return dummyNode.next;
    }
}

debug:Time Limit Exceeded

bug 描述

• 
• 错误代码
• 

解决过程

• 在结尾添这句，可以测试前面是否由正确执行交换操作
  • 
  • 执行结果
    • 
• 由此可知，我第一次 1 和 2 元素的交换成功了，但后续的交换没有按设想中进行
• 进而排查 cur.next 的指向是否有问题，发现是 temp1，看起来没问题，但 temp 作为 while 循环外的变量，其指向是没有变的。
• 如果我们想让 cur 在第二次循环中指向正确的 temp1 和 temp2, 那么就要把 temp 放到 while 内，每次新循环都重设它们的指向