迭代+头插法搞定两两交换链表中的节点 | IT宅-帅旋的专业知识分享

迭代+头插法搞定两两交换链表中的节点

发布于 2024-03-15 | 更新于 2024-08-21

链表

7

题目：24. 两两交换链表中的节点^[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

注意，这个题目也是针对单向链表操作的。两两交换链表中的节点要求在链表上进行节点位置的交换，而不仅仅是交换节点的值。

这里可以使用迭代法来实现。

解题思路

迭代方法的核心思想是遍历链表，每次跳过两个节点，并在遍历过程中交换每对相邻的节点。

1. 创建一个哨兵节点：这个哨兵节点指向链表的头节点，便于处理头节点的交换操作，同时作为返回值的参考。
2. 初始化指针：使用指针 prev 初始化为哨兵节点，逐个遍历节点。
3. 遍历并交换节点：在链表上移动指针，每次处理prev和后面两个节点的指针指向，进行节点的交换操作，最后把prev节点指向下一个节点继续处理。

Java解法

下面是使用Java语言的解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 哨兵节点，指向链表头节点
        ListNode dump = new ListNode();
        dump.next = head;
        ListNode prev = dump;
        while (prev.next != null && prev.next.next != null) {
            ListNode n1 = prev.next;
            ListNode n2 = prev.next.next;
          	// 修改三个指针指向
            prev.next = n2;
            n1.next = n2.next;
            n2.next = start;
          	// 继续往前迭代
            prev = start;
        }
        return dump.next;
    }
}

注意，这里修改三个指针方向比较容易出错，脑海里一定要有这样的图，做题的时候可以画出来：

References

---

1. 24. 两两交换链表中的节点 ↩︎

快慢指针：环形链表

迭代法轻松拿下反转链表