两两交换链表中的节点

2026-04-05 算法

两两交换链表中的节点

1. 题目描述

提示
题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

2. 解题思路

核心总结

核心思想：重新建立指向关系。引入 dummy 节点保证逻辑一致。通过三步翻转法：1号指向3号，2号指向1号，前驱指向2号。

💡 易错点

容易形成环：修改指向前需利用局部变量暂存节点。
循环条件：必须同时检查 pre.next (奇数长) 和 pre.next.next (偶数长)，且顺序不能反。

3. 代码实现

/**

 * 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 dummy = new ListNode(0,head);

        ListNode pre = dummy;

        while(pre.next != null && pre.next.next != null){

            ListNode cur = pre.next;

            ListNode next = pre.next.next;

            cur.next = next.next;

            next.next = cur;

            pre.next = next;

            pre = cur;

        }

        return dummy.next;

    }

}

4. 复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(1)$

5. 总结与反思

本文已被观测了次