[0024] 两两交换链表中的节点
发表于
本文字数：
1.6k
阅读时长 ≈
1 分钟
title: “[0024] 两两交换链表中的节点”
tags:
- leetcode
- 题解
- 链表
categories: - leetcode
- 题解
author: - 黄宁
comments: true
updated: true
permalink:
mathjax: true
top: false
description: …
date: 2020-04-17 11:09:24
[0024] 两两交换链表中的节点
- GitHub
- http://leetcode.xuezhisd.top/post/8b7b7fa4.html
- https://leetcode.com/problems/swap-nodes-in-pairs
- https://leetcode-cn.com/problems/swap-nodes-in-pairs
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定1->2->3->4, 你应该返回2->1->4->3.
Related Topics
题目解析
- [请一句话描述题目…]
不确定性
方法一：三指针迭代法
分析
- 设定一个指针指向奇数节点，另一个指针指向偶数节点，对两个节点进行交换
思路
- 建立一个前驱节点，并使用pre指针指向它
- 建立指针start指向奇数节点和指针end指向偶数节点
- 令pre的后继节点为end，令start为end的后继节点
- 调整3个指针的位置，顺序迭代，指导前驱节点pre的后继不存在（偶数个节点），或pre的后继的后继不存在（奇数个节点）
注意
- 链表中节点个数可能是奇数个或偶数个
知识点
- 链表中节点的插入
复杂度
- 时间复杂度 O(n)
- 空间复杂度 O(1)
代码
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
while (pre->next && pre->next->next){
ListNode* start = pre->next;
ListNode* end = start->next;
pre->next = end;
start->next = end->next;
end->next = start;
pre = start;
}
return dummy->next;
}
方法二：递归法
分析
- 交换的每一步都是类似的，将前一个节点的next指针指向后一个节点的后继节点，让后一个节点的next指针指向前一个节点
思路
- 定义指针start作为前一个节点，end作为后一个节点
- start的后继是“已经交换好的链表的头节点”，这是就要再次进入递归体
- end的后继是start
- 递归的出口是当前节点或当前节点的后继节点为空
注意
- 在交换完成后，后一个节点成为了前一个节点，因此需要返回的是后一个指针
知识点
- 递归
- 链表中节点的插入
复杂度
- 时间复杂度 O(N)
- 空间复杂度 O(N)
代码
ListNode* swapPairs(ListNode* head) {
//递归的出口
if (!head || !head->next){
return head;
}
ListNode* start = head;
ListNode* end = head->next;
//主体部分，和插入类似，先连后边节点，再连前边节点
//可以看作第一个节点的后一个节点是，后面已经交换好的链表的头节点
start->next = swapPairs(end->next);
end->next = start;
//因为后一个节点被换到前一个位置，所以返回后一个节点
return end;
}
相关题目
[0035] 搜索插入位置
...
[0031] 下一个排列
...
[0029] 两数相除
...
[0028] 实现 strStr()
...
[0027] 移除元素
...
[0026] 删除排序数组中的重复项
...
[0021] 合并两个有序链表
...
[0020] 有效的括号
...
[0019] 删除链表的倒数第N个节点
...
[0006] Z 字形变换
...
[0015] 三数之和
...
[0014] 最长公共前缀
...
[0009] 回文数
...
专题-随机化
...
专题-数学
...
专题-搜索算法
...
专题-图论
...
专题-数论
...
专题-贪心算法
...
专题-模拟算法
...
专题-枚举算法
...
专题-STL算法
...
专题-二分算法
...
专题-BFS算法
...
专题-DFS算法
...
专题-DP算法
...
专题-回溯算法
...
专题-递归算法
...
专题-查找算法
...
专题-排序算法
...
专题-二叉树
...
专题-队列
...
专题-栈
...
专题-堆
...
专题-链表
...
专题-数组
...
专题-字符串
...
[LCP 3] 机器人大冒险
...
[LCP 5] 发 LeetCoin
...
[LCP 2] 分式化简
...
[LCP 4] 覆盖
...
[LCP 1] 猜数字
...
[1368] 使网格图至少有一条有效路径的最小代价
...
[1367] 二叉树中的列表
...
[1366] 通过投票对团队排名
...
[1365] 有多少小于当前数字的数字
...
[1364] 顾客的可信联系人数量
...
[1363] 形成三的最大倍数
...