LeetCode: Swap Nodes in Pairs 解题报告
2024-08-31 16:27:01
Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
SOLUTION 1:
递归解法:
1. 先翻转后面的链表,得到新的Next.
2. 翻转当前的2个节点。
3. 返回新的头部。
// Solution 1: the recursion version.
public ListNode swapPairs1(ListNode head) {
if (head == null) {
return null;
} return rec(head);
} public ListNode rec(ListNode head) {
if (head == null || head.next == null) {
return head;
} ListNode next = head.next.next; // 翻转后面的链表
next = rec(next); // store the new head.
ListNode tmp = head.next; // reverse the two nodes.
head.next = next;
tmp.next = head; return tmp;
}
SOLUTION 2:
迭代解法:
1. 使用Dummy node保存头节点前一个节点
2. 记录翻转区域的Pre(上一个节点),记录翻转区域的next,或是tail。
3. 翻转特定区域,并不断前移。
有2种写法,后面一种写法稍微简单一点,记录的是翻转区域的下一个节点。
// Solution 2: the iteration version.
public ListNode swapPairs(ListNode head) {
// 如果小于2个元素,不需要任何操作
if (head == null || head.next == null) {
return head;
} ListNode dummy = new ListNode(0);
dummy.next = head; // The node before the reverse area;
ListNode pre = dummy; while (pre.next != null && pre.next.next != null) {
// The last node of the reverse area;
ListNode tail = pre.next.next; ListNode tmp = pre.next;
pre.next = tail; ListNode next = tail.next;
tail.next = tmp;
tmp.next = next; // move forward the pre node.
pre = tmp;
} return dummy.next;
}
// Solution 3: the iteration version.
public ListNode swapPairs3(ListNode head) {
// 如果小于2个元素,不需要任何操作
if (head == null || head.next == null) {
return head;
} ListNode dummy = new ListNode(0);
dummy.next = head; // The node before the reverse area;
ListNode pre = dummy; while (pre.next != null && pre.next.next != null) {
ListNode next = pre.next.next.next; ListNode tmp = pre.next;
pre.next = pre.next.next;
pre.next.next = tmp; tmp.next = next; // move forward the pre node.
pre = tmp;
} return dummy.next;
}
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/list/SwapPairs3.java
最新文章
- HTML5+CSS3+Jquery实现纯手工的垂直时光轴【附源码】
- MapWinGIS.ocx 注册
- SCU3033 Destroying a Painting(最小费用最大流)
- 【wikioi】2800 送外卖(状压dp+floyd)
- Java SimpleDateFormat 函数
- 转:阿里旺旺导致python安装包失败的解决办法
- Combination Sum —— LeetCode
- docker 基于现有镜像修改后保存,上传私有仓库
- 转:C++ 匿名namespace的作用以及它与static的区别
- java集合框架(hashSet自定义元素是否相同,重写hashCode和equals方法)
- postgis 中的距离计算
- Css3关键帧动画
- js new到底干了什么,new的意义是什么?
- 一个CSS+jQuery的放大缩小动画效果
- Deployment descriptor
- Docker镜像Push到DockerHub
- 关于flex的crossdomain.xml文件存放目录
- Apache服务器的安装与配置
- 关于Unity中Mecanim动画的重定向与动画混合
- WebService发布协议--SOAP和REST的区别