趣味算法题

越刷越上头的趣味算法题
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

迭代+头插法搞定两两交换链表中的节点

发布于 2024-03-15 | 更新于 2024-08-21

题目:24. 两两交换链表中的节点[1]

如果您已经有思路了,或者是N刷了,可以先自己写一遍。

题目分析

注意,这个题目也是针对单向链表操作的。两两交换链表中的节点要求在链表上进行节点位置的交换,而不仅仅是交换节点的值。

这里可以使用迭代法来实现。

解题思路

迭代方法的核心思想是遍历链表,每次跳过两个节点,并在遍历过程中交换每对相邻的节点。

  1. 创建一个哨兵节点:这个哨兵节点指向链表的头节点,便于处理头节点的交换操作,同时作为返回值的参考。
  2. 初始化指针:使用指针 prev 初始化为哨兵节点,逐个遍历节点。
  3. 遍历并交换节点:在链表上移动指针,每次处理prev和后面两个节点的指针指向,进行节点的交换操作,最后把prev节点指向下一个节点继续处理。

Java解法

下面是使用Java语言的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 哨兵节点,指向链表头节点
ListNode dump = new ListNode();
dump.next = head;
ListNode prev = dump;
while (prev.next != null && prev.next.next != null) {
ListNode n1 = prev.next;
ListNode n2 = prev.next.next;
// 修改三个指针指向
prev.next = n2;
n1.next = n2.next;
n2.next = start;
// 继续往前迭代
prev = start;
}
return dump.next;
}
}

注意,这里修改三个指针方向比较容易出错,脑海里一定要有这样的图,做题的时候可以画出来:

image-20240315220210323

References


  1. 24. 两两交换链表中的节点 ↩︎

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/algorithm/swap-nodes-in-pairs.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。