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

LeetCode LeetCode 热题100 链表 递归
发布时间 :
字数:1.7k 阅读 : 评论:
  1. 24.两两交换链表中的节点
    1. 24.1 题目
    2. 24.2 题解
      1. 方法一：递归交换节点
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：迭代交换节点
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 24.3 代码
    4. 24.4 运行结果

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

24.1 题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

24.2 题解

方法一：递归交换节点

思路

递归处理链表：先交换后面的节点，再处理当前两个节点。对于当前两个节点，将第一个节点的 next 指向递归处理后的结果，第二个节点的 next 指向第一个节点，返回第二个节点作为新的头节点。

核心思想：每次递归处理一对节点，将第二个节点作为新的头节点返回。

具体步骤：

  1. 终止条件：链表为空或只有一个节点，直接返回。
  2. 记录当前两个节点：first = head，second = head.next。
  3. 递归处理剩余部分：first.next = SwapPairs(second.next)。
  4. 交换当前两个节点：second.next = first。
  5. 返回 second 作为新的头节点。

举例：对于链表 1 → 2 → 3 → 4：

  • 处理 1 → 2：
    • first = 1，second = 2
    • first.next = SwapPairs(3 → 4) → 返回 4 → 3
    • second.next = first → 2 → 1 → 4 → 3
    • 返回 2
  • 最终结果：2 → 1 → 4 → 3

复杂度分析

  • 时间复杂度：O(n)，每个节点访问一次。
  • 空间复杂度：O(n)，递归栈深度。

代码

// 方法一：递归交换节点
static ListNode SwapPairs1(ListNode head)
{
    // 如果链表为空或者只有一个节点，直接返回
    if (head == null || head.next == null)
    {
        return head;
    }

    // 交换相邻的两个节点
    ListNode first = head;
    ListNode second = head.next;

    // 递归地对剩余节点进行相邻交换
    first.next = SwapPairs1(second.next);
    second.next = first;

    // 返回交换后的头节点
    return second;
}

方法二：迭代交换节点

思路

创建虚拟头节点简化边界处理。用 prev 指针记录前一对节点的末尾，每次交换当前两个相邻节点，然后更新 prev 和当前指针继续处理下一对。

核心思想：虚拟头节点统一处理「第一对节点」，prev 指针连接已交换部分和待交换部分。

具体步骤：

  1. 创建虚拟头节点 dummy，dummy.next = head。
  2. 用 prev 指向已交换部分的末尾，cur 指向待交换部分的第一个节点。
  3. 当 cur 和 cur.next 都存在时：
    • 记录 first = cur，second = cur.next
    • 交换：prev.next = second，first.next = second.next，second.next = first
    • 更新：prev = first，cur = first.next
  4. 返回 dummy.next。

举例：对于链表 1 → 2 → 3 → 4：

  • 初始：dummy → 1 → 2 → 3 → 4，prev = dummy，cur = 1
  • 第一轮交换：
    • first = 1，second = 2
    • prev.next = 2，first.next = 3，second.next = 1
    • 结果：dummy → 2 → 1 → 3 → 4
    • prev = 1，cur = 3
  • 第二轮交换：
    • first = 3，second = 4
    • prev.next = 4，first.next = null，second.next = 3
    • 结果：dummy → 2 → 1 → 4 → 3
    • prev = 3，cur = null
  • cur 为空，结束，返回 dummy.next：2 → 1 → 4 → 3

复杂度分析

  • 时间复杂度：O(n)，遍历一次链表。
  • 空间复杂度：O(1)，只使用指针变量。

代码

// 方法二：迭代交换节点
static ListNode SwapPairs2(ListNode cur)
{
    // 创建虚拟头节点，简化操作
    ListNode dummy = new ListNode(0);
    dummy.next = cur;
    ListNode prev = dummy;

    // 当还有至少两个相邻节点时继续交换
    while (cur != null && cur.next != null)
    {
        // 记录要交换的两个节点
        ListNode first = cur;
        ListNode second = cur.next;

        // 实现交换
        prev.next = second;
        first.next = second.next;
        second.next = first;

        // 移动到下一对节点
        prev = first;
        cur = first.next;
    }

    // 返回交换后的链表头
    return dummy.next;
}

24.3 代码

using System;

// 链表节点定义
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
        // 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

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

        // 示例 2：
        // 输入：head = []
        // 输出：[]

        // 示例 3：
        // 输入：head = [1]
        // 输出：[1]

        // 提示：
        // - 链表中节点的数目在范围 [0, 100] 内
        // - 0 <= Node.val <= 100

        #endregion

        #region 测试

        // 示例 1 测试
        ListNode head1 = GenerateList(new int[] { 1, 2, 3, 4 });
        Console.Write("示例1 方法1 输出：");
        PrintList(head1);
        ListNode swappedHead1 = SwapPairs1(head1);
        Console.Write(" --> ");
        PrintList(swappedHead1);

        ListNode head1_2 = GenerateList(new int[] { 1, 2, 3, 4 });
        Console.Write("示例1 方法2 输出：");
        PrintList(head1_2);
        ListNode swappedHead1_2 = SwapPairs2(head1_2);
        Console.Write(" --> ");
        PrintList(swappedHead1_2);

        // 示例 2 测试
        ListNode head2 = GenerateList(new int[] { });
        Console.Write("示例2 方法1 输出：");
        PrintList(head2);
        ListNode swappedHead2 = SwapPairs1(head2);
        Console.Write(" --> ");
        PrintList(swappedHead2);

        ListNode head2_2 = GenerateList(new int[] { });
        Console.Write("示例2 方法2 输出：");
        PrintList(head2_2);
        ListNode swappedHead2_2 = SwapPairs2(head2_2);
        Console.Write(" --> ");
        PrintList(swappedHead2_2);

        // 示例 3 测试
        ListNode head3 = GenerateList(new int[] { 1 });
        Console.Write("示例3 方法1 输出：");
        PrintList(head3);
        ListNode swappedHead3 = SwapPairs1(head3);
        Console.Write(" --> ");
        PrintList(swappedHead3);

        ListNode head3_2 = GenerateList(new int[] { 1 });
        Console.Write("示例3 方法2 输出：");
        PrintList(head3_2);
        ListNode swappedHead3_2 = SwapPairs2(head3_2);
        Console.Write(" --> ");
        PrintList(swappedHead3_2);

        #endregion
    }

    #region 答案

    // 方法一：递归交换节点
    static ListNode SwapPairs1(ListNode head)
    {
        // 如果链表为空或者只有一个节点，直接返回
        if (head == null || head.next == null)
        {
            return head;
        }

        // 交换相邻的两个节点
        ListNode first = head;
        ListNode second = head.next;

        // 递归地对剩余节点进行相邻交换
        first.next = SwapPairs1(second.next);
        second.next = first;

        // 返回交换后的头节点
        return second;
    }

    // 方法二：迭代交换节点
    static ListNode SwapPairs2(ListNode cur)
    {
        // 创建虚拟头节点，简化操作
        ListNode dummy = new ListNode(0);
        dummy.next = cur;
        ListNode prev = dummy;

        // 当还有至少两个相邻节点时继续交换
        while (cur != null && cur.next != null)
        {
            // 记录要交换的两个节点
            ListNode first = cur;
            ListNode second = cur.next;

            // 实现交换
            prev.next = second;
            first.next = second.next;
            second.next = first;

            // 移动到下一对节点
            prev = first;
            cur = first.next;
        }

        // 返回交换后的链表头
        return dummy.next;
    }

    #endregion

    #region 辅助方法

    // 根据数组生成链表
    static ListNode GenerateList(int[] nums)
    {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        foreach (var num in nums)
        {
            current.next = new ListNode(num);
            current = current.next;
        }

        return dummy.next;
    }

    // 打印链表
    static void PrintList(ListNode head)
    {
        while (head != null)
        {
            Console.Write(head.val + " ");
            head = head.next;
        }

        Console.WriteLine();
    }

    #endregion
}

24.4 运行结果

示例1 方法1 输出：1 2 3 4 
 --> 2 1 4 3 
示例1 方法2 输出：1 2 3 4 
 --> 2 1 4 3 
示例2 方法1 输出：
 --> 
示例2 方法2 输出：
 --> 
示例3 方法1 输出：1 
 --> 1 
示例3 方法2 输出：1 
 --> 1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏