题目链接

两两交换链表中的结点

题目描述

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

注意：

  • 你不能只是单纯地改变节点内部的值，而是需要实际地进行节点交换。
  • 链表中的节点数目在 范围内。

这是一个核心代码模式 (Core Code Mode) 的题目，你只需要实现 swapPairs 函数即可。

示例: 输入: {1,2,3,4} (表示链表 1 -> 2 -> 3 -> 4)

输出: {2,1,4,3} (表示链表 2 -> 1 -> 4 -> 3)

解题思路

这个问题要求我们将链表中的节点每两个一组进行交换。例如，1->2->3->4 变成 2->1->4->3。我们可以使用递归或迭代两种方法来解决。

方法一：递归

递归是一种非常直观和优雅的解决方式。

  • 基本思想：将"两两交换链表"这个问题分解为"交换当前两个节点" + "两两交换剩下链表"的子问题。
  • 递归终止条件：当链表为空或只有一个节点时，无法进行交换，直接返回头节点 head。
  • 递归过程：
    1. 设当前链表头节点为 head，第二个节点为 newHead。
    2. 我们需要将 head 和 newHead 交换。交换后，新的头节点是 newHead。
    3. newHead 的 next 指针应该指向 head。
    4. head 的 next 指针应该指向 对剩余链表 (newHead 原本的 next) 进行两两交换后的结果。这正是递归调用的地方：swapPairs(newHead.next)。
    5. 返回 newHead 作为已交换部分的头节点。

这个过程将链表从头到尾两两配对，并自底向上地完成交换连接。

方法二：迭代 (使用虚拟头节点)

迭代方法可以避免递归带来的额外空间开销。

  • 基本思想：使用一个虚拟头节点 dummy 来简化对头节点的处理。dummy.next 指向原始头节点。我们还需要一个指针 prev 来追踪每一对要交换节点的前一个节点。
  • 迭代过程：
    1. 初始化 dummy 节点，并让 dummy.next = head。设置 prev = dummy。
    2. 当 prev 后面至少还有两个节点时，循环继续： a. 定义要交换的两个节点：node1 = prev.next 和 node2 = node1.next。 b. 执行交换： - prev.next = node2 (前驱节点指向第二个节点) - node1.next = node2.next (第一个节点指向第三个节点) - node2.next = node1 (第二个节点指向第一个节点) c. 更新 prev 为 node1，准备下一轮交换。
    3. 循环结束后，dummy.next 就是新链表的头节点。

两种方法都能解决问题，递归代码更简洁，而迭代在空间效率上更优。

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* swapPairs(ListNode* head) {
        // 递归终止条件：链表为空或只有一个节点，无需交换
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // 获取第二个节点，它将成为新的头节点
        ListNode* newHead = head->next;
        
        // 原头节点的 next 指向下一组交换后的头节点
        head->next = swapPairs(newHead->next);
        
        // 新头节点的 next 指向原头节点，完成交换
        newHead->next = head;
        
        return newHead;
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode swapPairs(ListNode head) {
        // 递归终止条件：链表为空或只有一个节点，无需交换
        if (head == null || head.next == null) {
            return head;
        }

        // 获取第二个节点，它将成为新的头节点
        ListNode newHead = head.next;

        // 原头节点的 next 指向下一组交换后的头节点
        head.next = swapPairs(newHead.next);

        // 新头节点的 next 指向原头节点，完成交换
        newHead.next = head;

        return newHead;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 递归终止条件：链表为空或只有一个节点，无需交换
        if not head or not head.next:
            return head
        
        # 获取第二个节点，它将成为新的头节点
        new_head = head.next
        
        # 原头节点的 next 指向下一组交换后的头节点
        head.next = self.swapPairs(new_head.next)
        
        # 新头节点的 next 指向原头节点，完成交换
        new_head.next = head
        
        return new_head

算法及复杂度

  • 算法: 递归 (或 迭代)
  • 时间复杂度: ，其中 是链表的节点数。因为我们需要遍历每个节点一次来完成交换。
  • 空间复杂度:
    • 递归解法: 。在最坏的情况下，递归栈的深度可以达到 ，这会占用 的栈空间。
    • 迭代解法: 。我们只使用了常数个额外的指针变量，与链表大小无关。