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

文章目录

• 题目链接
• 题目描述
• 解题思路
• 题解代码
• 复杂度分析

题目链接

https://leetcode.cn/problems/swap-nodes-in-pairs/

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

不能修改节点内部的值（即只能实际交换节点）。

解题思路

• 使用哑节点 dummy 简化头结点被交换的处理。
• 维护四个指针：
  • node0：当前待交换对的前驱节点（初始为 dummy）
  • node1：当前对的第一个节点
  • node2：当前对的第二个节点
  • node3：下一对的起始节点（node2 的后继）
• 交换步骤（重连指针）：
  • node0.next = node2
  • node2.next = node1
  • node1.next = node3
• 然后将 node0 移到 node1，将 node1 移到 node3，继续处理下一对。
• 循环条件为 node1 与 node1.next 都非空，保证成对交换。

题解代码

classSolution{publicListNodeswapPairs(ListNode head){ListNode dummy =newListNode(0, head);ListNode node0 = dummy;ListNode node1 = head;while(node1 !=null&& node1.next !=null){ListNode node2 = node1.next;ListNode node3 = node2.next;// 断开并重连，完成一对交换 node0.next = node2; node2.next = node1; node1.next = node3;// 移动到下一对 node0 = node1; node1 = node3;}return dummy.next;}}

复杂度分析

• 时间复杂度：O(n)，每个节点至多被访问和指针重连一次。
• 空间复杂度：O(1)，只使用常数个指针。