当前位置: 首页 > news >正文

两两交换链表中的节点-leetcode

题目描述

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

示例 1:

img

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

示例 2:

输入:head = []
输出:[]

示例 3:

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

提示:

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

解法一

思路:

采用递归的方法。两两之间进行交换,交换完成后后续的部分进行新的交换。

代码:

/*** 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 void swap(ListNode head) {if(head.next == null||head.next.next==null) return;ListNode last;if(head.next.next.next!=null)last=head.next.next.next;else last=null;ListNode first=head.next;ListNode second=head.next.next;head.next=second;second.next=first;first.next=last;swap(first);}public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0, head);swap(dummy);return dummy.next;}
}//进一步简化版本
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = head.next;head.next = swapPairs(newHead.next);newHead.next = head;return newHead;}
}

解法二

思路:

来自官方题解。

也可以通过迭代的方式实现两两交换链表中的节点。

创建哑结点 dummyHead,令 dummyHead.next = head。令 temp 表示当前到达的节点,初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。

如果 temp 的后面没有节点或者只有一个节点,则没有更多的节点需要交换,因此结束交换。否则,获得 temp 后面的两个节点 node1 和 node2,通过更新节点的指针关系实现两两交换节点。

具体而言,交换之前的节点关系是 temp -> node1 -> node2,交换之后的节点关系要变成 temp -> node2 -> node1,因此需要进行如下操作。

temp.next = node2
node1.next = node2.next
node2.next = node1

完成上述操作之后,节点关系即变成 temp -> node2 -> node1。再令 temp = node1,对链表中的其余节点进行两两交换,直到全部节点都被两两交换。

两两交换链表中的节点之后,新的链表的头节点是 dummyHead.next,返回新的链表的头节点即可。

代码:

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;}
}
http://www.hskmm.com/?act=detail&tid=36936

相关文章:

  • 算法第二章实践作业
  • 解决homebrew下载报错问题
  • 软考中级学习总结(5)
  • 软考中级学习总结(4)
  • 每日反思(2025_10_22)
  • docker: Error response from daemon: failed to set up container networking 解决办法
  • 实验2 现代C++编程初体验
  • CSP-S36
  • 新学期每日总结(第13天)
  • GCM(Galois/Counter Mode) 认证加密算法实现
  • 【学习笔记】slope-trick
  • 10.13-10.19学习做题笔记
  • 2025.10.22
  • yny计数题记录
  • 20232404 2025-2026-2 《网络与系统攻防技术》实验二实验报告
  • 1020302118兰逸霏的第一次作业
  • ubuntu 25.10 修改源 - ldx
  • pytorch学习笔记(1)
  • 20232318 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 《中华人民共和国网络安全法》第二十一条这一核心考点
  • 嵌入式软件分层架构设计 - lucky
  • DP 基础题乱做
  • [题解]P4616 [COCI 2017/2018 #5] Pictionary
  • 二三级区别
  • 第九章-Where-1S-tHe-Hacker
  • CF 2023D Many Games
  • 2025.10.22考试记录
  • 2025多校冲刺CSP模拟赛7 题目分析
  • Typora的多端同步方案,如何多台计算机共享md文件?Windows和Mac通过定时执行git来同步markdown文件
  • Trie树