Hot 100 --- 两两交换链表中的节点

本文概览本文以LeetCode经典题目两两交换链表中的节点为例重点讲解如何通过哑节点解决新头节点问题如何用prev、first、second三个指针完成两两交换以及如何判断循环结束条件一、题目二、题目分析给定一个链表两两交换其中相邻的节点并返回交换后链表的头节点目标交换节点本身而不是只交换节点值核心难点链表节点交换本质上是指针重连容易断链或者丢失后续节点这道题主要有三个问题需要解决怎么返回新的头节点怎么交换两个相邻节点循环什么时候结束思路概览Java实现代码如下public ListNode swapPairs(ListNode head) { if (head null || head.next null) { return head; } // 创建哑节点 ListNode dummy new ListNode(0, head); // 初始化前指针 ListNode prev dummy; // 交换后面两个节点 ListNode first; ListNode second; // 交换节点 while (prev.next ! null prev.next.next ! null) { first prev.next; second first.next; // 交换节点 prev.next second; first.next second.next; second.next first; // 更新前指针 prev first; } return dummy.next; }思路简要说明哑节点解决头节点变化交换第一对节点后新的头节点会变成原来的第二个节点所以用dummy指向原头节点最后返回dummy.next三个指针完成交换prev指向当前要交换的一对节点的前一个节点first和second分别指向要交换的两个节点判断是否还能交换只有prev.next和prev.next.next都不为空时后面才至少有两个节点才能继续交换三、思路详解问题一怎么返回新的头节点两两交换后链表的头节点可能会改变比如原链表1 → 2 → 3 → 4 交换后2 → 1 → 4 → 3原来的头节点是 1交换之后新的头节点变成了 2。如果直接拿原来的head返回就会返回错误最简单的解决办法是创建一个哑节点ListNode dummy new ListNode(0, head);让dummy.next指向原来的头节点。这样无论头节点怎么变化dummy始终在链表最前面最后返回dummy.next即可dummy → 1 → 2 → 3 → 4 ↑ head 交换第一对后 dummy → 2 → 1 → 3 → 4 ↑ dummy.next新的头节点 ↑ head原来的头节点1已经不是头节点了 返回 dummy.next也就是 2可以看到如果仍然返回原来的head返回的是节点 1会丢失前面的节点 2而返回dummy.next就能拿到真正的新头节点问题二怎么判断是否还能继续交换两两交换的前提是后面至少还有两个节点对于奇数个节点的链表最后一个节点无法交换1 → 2 → 3 → 4 → 5 交换后2 → 1 → 4 → 3 → 5最后的 5 没有配对节点所以保持不变在代码中我们用prev指向当前要交换的一对节点的前一个节点。那么要判断后面是否还有两个节点只需要看while (prev.next ! null prev.next.next ! null)prev.next ! null说明后面至少还有第一个节点prev.next.next ! null说明后面至少还有第二个节点只有两个条件都满足才能进行交换。只要其中一个为 null就说明剩下的节点构不成一对循环结束问题三怎么交换两个相邻节点这是本题最关键、也最抽象的地方假设当前链表片段如下prev → first → second → next我们想把first和second交换变成prev → second → first → next其中first prev.next; second first.next;也就是说first和second这两个节点已经被变量记录下来了所以交换过程中不用担心丢失它们。真正需要注意的是交换后还要让后面的next链表保持不变交换步骤交换的三行代码是prev.next second; first.next second.next; second.next first;我们逐步看第一步让 prev 指向 secondprev.next second;原来prev → first → second → next 现在prev → second → next first ────────↑first暂时还指向second