24.总结

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 题解

递归交换节点

// 方法一：递归交换节点
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;
}

---

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