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
