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

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯地改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

Java 实现解法

方法：迭代

java">/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode curr = dummy;while (curr.next != null && curr.next.next != null) {ListNode first = curr.next;ListNode second = curr.next.next;// 交换节点first.next = second.next;curr.next = second;second.next = first;// 移动到下一对节点curr = first;}return dummy.next;}
}

解题思路

• 迭代方法：从头节点开始遍历链表，检查当前节点的下一个节点是否不为空（即有节点可以交换）。
  • 如果有节点可以交换，那么获取当前节点的下一个节点（first）和下下一个节点（second）。
  • 将 first 节点的 next 指向 second 节点的 next，从而将 second 节点从链表中断开。
  • 将 curr 节点的 next 指向 second 节点，将 second 节点插入到 curr 节点之后。
  • 将 second 节点的 next 指向 first 节点，完成节点的交换。
  • 更新 curr 指针到 first 节点，以便下一次迭代交换下一对节点。
• 处理边界情况：如果链表为空或者只有一个节点，直接返回头节点，因为没有节点可以交换。

这种方法的时间复杂度是 O(n)，其中 n 是链表的长度。空间复杂度是 O(1)，因为我们只使用了有限的额外空间来存储指针。这种方法简单且高效，是解决链表节点交换问题的标准方法。

注：题目来源leetcode网站