mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
528 lines
15 KiB
Markdown
Executable File
528 lines
15 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
# 24. 两两交换链表中的节点
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/swap-nodes-in-pairs/)
|
||
|
||
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
|
||
|
||
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
|
||
|
||
|
||
<img src='https://file1.kamacoder.com/i/algo/24.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9-%E9%A2%98%E6%84%8F.jpg' width=600 alt='24.两两交换链表中的节点-题意'> </img></div>
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点](https://www.bilibili.com/video/BV1YT411g7br)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
## 思路
|
||
|
||
|
||
这道题目正常模拟就可以了。
|
||
|
||
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
|
||
|
||
对虚拟头结点的操作，还不熟悉的话，可以看这篇[链表：听说用虚拟头节点会方便很多？](https://programmercarl.com/0203.移除链表元素.html)。
|
||
|
||
接下来就是交换相邻两个元素了，**此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序**
|
||
|
||
初始时，cur指向虚拟头结点，然后进行如下三步：
|
||
|
||
|
||
|
||
操作之后，链表如下：
|
||
|
||
|
||
|
||
看这个可能就更直观一些了：
|
||
|
||
|
||
|
||
|
||
对应的C++代码实现如下： （注释中详细和如上图中的三步做对应）
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
ListNode* swapPairs(ListNode* head) {
|
||
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
|
||
dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
|
||
ListNode* cur = dummyHead;
|
||
while(cur->next != nullptr && cur->next->next != nullptr) {
|
||
ListNode* tmp = cur->next; // 记录临时节点
|
||
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
|
||
|
||
cur->next = cur->next->next; // 步骤一
|
||
cur->next->next = tmp; // 步骤二
|
||
cur->next->next->next = tmp1; // 步骤三
|
||
|
||
cur = cur->next->next; // cur移动两位，准备下一轮交换
|
||
}
|
||
ListNode* result = dummyHead->next;
|
||
delete dummyHead;
|
||
return result;
|
||
}
|
||
};
|
||
```
|
||
|
||
* 时间复杂度：O(n)
|
||
* 空间复杂度：O(1)
|
||
|
||
## 拓展
|
||
|
||
**这里还是说一下，大家不必太在意力扣上执行用时，打败多少多少用户，这个统计不准确的。**
|
||
|
||
做题的时候自己能分析出来时间复杂度就可以了，至于力扣上执行用时，大概看一下就行。
|
||
|
||
上面的代码我第一次提交执行用时8ms，打败6.5%的用户，差点吓到我了。
|
||
|
||
心想应该没有更好的方法了吧，也就 $O(n)$ 的时间复杂度，重复提交几次，这样了：
|
||
|
||
|
||
|
||
力扣上的统计如果两份代码是 100ms 和 300ms的耗时，其实是需要注意的。
|
||
|
||
如果一个是 4ms 一个是 12ms，看上去好像是一个打败了80%，一个打败了20%，其实是没有差别的。 只不过是力扣上统计的误差而已。
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### C:
|
||
|
||
```c
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* struct ListNode {
|
||
* int val;
|
||
* struct ListNode *next;
|
||
* };
|
||
*/
|
||
//递归版本
|
||
struct ListNode* swapPairs(struct ListNode* head){
|
||
//递归结束条件：头节点不存在或头节点的下一个节点不存在。此时不需要交换，直接返回head
|
||
if(!head || !head->next)
|
||
return head;
|
||
//创建一个节点指针类型保存头结点下一个节点
|
||
struct ListNode *newHead = head->next;
|
||
//更改头结点+2位节点后的值，并将头结点的next指针指向这个更改过的list
|
||
head->next = swapPairs(newHead->next);
|
||
//将新的头结点的next指针指向老的头节点
|
||
newHead->next = head;
|
||
return newHead;
|
||
}
|
||
```
|
||
|
||
```c
|
||
//迭代版本
|
||
struct ListNode* swapPairs(struct ListNode* head){
|
||
//使用双指针避免使用中间变量
|
||
typedef struct ListNode ListNode;
|
||
ListNode *fakehead = (ListNode *)malloc(sizeof(ListNode));
|
||
fakehead->next = head;
|
||
ListNode* right = fakehead->next;
|
||
ListNode* left = fakehead;
|
||
while(left && right && right->next ){
|
||
left->next = right->next;
|
||
right->next = left->next->next;
|
||
left->next->next = right;
|
||
left = right;
|
||
right = left->next;
|
||
}
|
||
return fakehead->next;
|
||
}
|
||
```
|
||
|
||
### Java：
|
||
|
||
```Java
|
||
// 递归版本
|
||
class Solution {
|
||
public ListNode swapPairs(ListNode head) {
|
||
// base case 退出提交
|
||
if(head == null || head.next == null) return head;
|
||
// 获取当前节点的下一个节点
|
||
ListNode next = head.next;
|
||
// 进行递归
|
||
ListNode newNode = swapPairs(next.next);
|
||
// 这里进行交换
|
||
next.next = head;
|
||
head.next = newNode;
|
||
|
||
return next;
|
||
}
|
||
}
|
||
```
|
||
|
||
```java
|
||
class Solution {
|
||
public ListNode swapPairs(ListNode head) {
|
||
ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
|
||
dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
|
||
ListNode cur = dumyhead;
|
||
ListNode temp; // 临时节点，保存两个节点后面的节点
|
||
ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
|
||
ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
|
||
while (cur.next != null && cur.next.next != null) {
|
||
temp = cur.next.next.next;
|
||
firstnode = cur.next;
|
||
secondnode = cur.next.next;
|
||
cur.next = secondnode; // 步骤一
|
||
secondnode.next = firstnode; // 步骤二
|
||
firstnode.next = temp; // 步骤三
|
||
cur = firstnode; // cur移动，准备下一轮交换
|
||
}
|
||
return dumyhead.next;
|
||
}
|
||
}
|
||
```
|
||
|
||
```java
|
||
// 将步骤 2,3 交换顺序，这样不用定义 temp 节点
|
||
public ListNode swapPairs(ListNode head) {
|
||
ListNode dummy = new ListNode(0, head);
|
||
ListNode cur = dummy;
|
||
while (cur.next != null && cur.next.next != null) {
|
||
ListNode node1 = cur.next;// 第 1 个节点
|
||
ListNode node2 = cur.next.next;// 第 2 个节点
|
||
cur.next = node2; // 步骤 1
|
||
node1.next = node2.next;// 步骤 3
|
||
node2.next = node1;// 步骤 2
|
||
cur = cur.next.next;
|
||
}
|
||
return dummy.next;
|
||
}
|
||
```
|
||
|
||
### Python：
|
||
|
||
```python
|
||
# 递归版本
|
||
# Definition for singly-linked list.
|
||
# class ListNode:
|
||
# def __init__(self, val=0, next=None):
|
||
# self.val = val
|
||
# self.next = next
|
||
|
||
class Solution:
|
||
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
|
||
if head is None or head.next is None:
|
||
return head
|
||
|
||
# 待翻转的两个node分别是pre和cur
|
||
pre = head
|
||
cur = head.next
|
||
next = head.next.next
|
||
|
||
cur.next = pre # 交换
|
||
pre.next = self.swapPairs(next) # 将以next为head的后续链表两两交换
|
||
|
||
return cur
|
||
```
|
||
|
||
```python
|
||
# Definition for singly-linked list.
|
||
# class ListNode:
|
||
# def __init__(self, val=0, next=None):
|
||
# self.val = val
|
||
# self.next = next
|
||
|
||
class Solution:
|
||
def swapPairs(self, head: ListNode) -> ListNode:
|
||
dummy_head = ListNode(next=head)
|
||
current = dummy_head
|
||
|
||
# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了
|
||
while current.next and current.next.next:
|
||
temp = current.next # 防止节点修改
|
||
temp1 = current.next.next.next
|
||
|
||
current.next = current.next.next
|
||
current.next.next = temp
|
||
temp.next = temp1
|
||
current = current.next.next
|
||
return dummy_head.next
|
||
|
||
```
|
||
|
||
### Go：
|
||
|
||
```go
|
||
func swapPairs(head *ListNode) *ListNode {
|
||
dummy := &ListNode{
|
||
Next: head,
|
||
}
|
||
//head=list[i]
|
||
//pre=list[i-1]
|
||
pre := dummy
|
||
for head != nil && head.Next != nil {
|
||
pre.Next = head.Next
|
||
next := head.Next.Next
|
||
head.Next.Next = head
|
||
head.Next = next
|
||
//pre=list[(i+2)-1]
|
||
pre = head
|
||
//head=list[(i+2)]
|
||
head = next
|
||
}
|
||
return dummy.Next
|
||
}
|
||
```
|
||
|
||
```go
|
||
// 递归版本
|
||
func swapPairs(head *ListNode) *ListNode {
|
||
if head == nil || head.Next == nil {
|
||
return head
|
||
}
|
||
next := head.Next
|
||
head.Next = swapPairs(next.Next)
|
||
next.Next = head
|
||
return next
|
||
}
|
||
```
|
||
|
||
### JavaScript:
|
||
|
||
```javascript
|
||
var swapPairs = function (head) {
|
||
let ret = new ListNode(0, head), temp = ret;
|
||
while (temp.next && temp.next.next) {
|
||
let cur = temp.next.next, pre = temp.next;
|
||
pre.next = cur.next;
|
||
cur.next = pre;
|
||
temp.next = cur;
|
||
temp = pre;
|
||
}
|
||
return ret.next;
|
||
};
|
||
```
|
||
|
||
```javascript
|
||
// 递归版本
|
||
var swapPairs = function (head) {
|
||
if (head == null || head.next == null) {
|
||
return head;
|
||
}
|
||
|
||
let after = head.next;
|
||
head.next = swapPairs(after.next);
|
||
after.next = head;
|
||
|
||
return after;
|
||
};
|
||
```
|
||
|
||
### TypeScript：
|
||
|
||
```typescript
|
||
function swapPairs(head: ListNode | null): ListNode | null {
|
||
const dummyNode: ListNode = new ListNode(0, head);
|
||
let curNode: ListNode | null = dummyNode;
|
||
while (curNode && curNode.next && curNode.next.next) {
|
||
let firstNode: ListNode = curNode.next,
|
||
secNode: ListNode = curNode.next.next,
|
||
thirdNode: ListNode | null = curNode.next.next.next;
|
||
curNode.next = secNode;
|
||
secNode.next = firstNode;
|
||
firstNode.next = thirdNode;
|
||
curNode = firstNode;
|
||
}
|
||
return dummyNode.next;
|
||
};
|
||
```
|
||
|
||
### Kotlin:
|
||
|
||
```kotlin
|
||
fun swapPairs(head: ListNode?): ListNode? {
|
||
val dummyNode = ListNode(0).apply {
|
||
this.next = head
|
||
}
|
||
var cur: ListNode? = dummyNode
|
||
while (cur?.next != null && cur.next?.next != null) {
|
||
val temp = cur.next
|
||
val temp2 = cur.next?.next?.next
|
||
cur.next = cur.next?.next
|
||
cur.next?.next = temp
|
||
cur.next?.next?.next = temp2
|
||
cur = cur.next?.next
|
||
}
|
||
return dummyNode.next
|
||
}
|
||
```
|
||
|
||
### Swift:
|
||
|
||
```swift
|
||
func swapPairs(_ head: ListNode?) -> ListNode? {
|
||
if head == nil || head?.next == nil {
|
||
return head
|
||
}
|
||
let dummyHead: ListNode = ListNode(-1, head)
|
||
var current: ListNode? = dummyHead
|
||
while current?.next != nil && current?.next?.next != nil {
|
||
let temp1 = current?.next
|
||
let temp2 = current?.next?.next?.next
|
||
|
||
current?.next = current?.next?.next
|
||
current?.next?.next = temp1
|
||
current?.next?.next?.next = temp2
|
||
|
||
current = current?.next?.next
|
||
}
|
||
return dummyHead.next
|
||
}
|
||
```
|
||
### Scala:
|
||
|
||
```scala
|
||
// 虚拟头节点
|
||
object Solution {
|
||
def swapPairs(head: ListNode): ListNode = {
|
||
var dummy = new ListNode(0, head) // 虚拟头节点
|
||
var pre = dummy
|
||
var cur = head
|
||
// 当pre的下一个和下下个都不为空，才进行两两转换
|
||
while (pre.next != null && pre.next.next != null) {
|
||
var tmp: ListNode = cur.next.next // 缓存下一次要进行转换的第一个节点
|
||
pre.next = cur.next // 步骤一
|
||
cur.next.next = cur // 步骤二
|
||
cur.next = tmp // 步骤三
|
||
// 下面是准备下一轮的交换
|
||
pre = cur
|
||
cur = tmp
|
||
}
|
||
// 最终返回dummy虚拟头节点的下一个，return可以省略
|
||
dummy.next
|
||
}
|
||
}
|
||
```
|
||
|
||
### PHP:
|
||
|
||
```php
|
||
//虚拟头结点
|
||
function swapPairs($head) {
|
||
if ($head == null || $head->next == null) {
|
||
return $head;
|
||
}
|
||
|
||
$dummyNode = new ListNode(0, $head);
|
||
$preNode = $dummyNode; //虚拟头结点
|
||
$curNode = $head;
|
||
$nextNode = $head->next;
|
||
while($curNode && $nextNode) {
|
||
$nextNextNode = $nextNode->next; //存下一个节点
|
||
$nextNode->next = $curNode; //交换curHead 和 nextHead
|
||
$curNode->next = $nextNextNode;
|
||
$preNode->next = $nextNode; //上一个节点的下一个指向指向nextHead
|
||
|
||
//更新当前的几个指针
|
||
$preNode = $preNode->next->next;
|
||
$curNode = $nextNextNode;
|
||
$nextNode = $nextNextNode->next;
|
||
}
|
||
|
||
return $dummyNode->next;
|
||
}
|
||
|
||
//递归版本
|
||
function swapPairs($head)
|
||
{
|
||
// 终止条件
|
||
if ($head === null || $head->next === null) {
|
||
return $head;
|
||
}
|
||
|
||
//结果要返回的头结点
|
||
$next = $head->next;
|
||
$head->next = $this->swapPairs($next->next); //当前头结点->next指向更新
|
||
$next->next = $head; //当前第二个节点的->next指向更新
|
||
return $next; //返回翻转后的头结点
|
||
}
|
||
```
|
||
|
||
### Rust:
|
||
|
||
```rust
|
||
// 虚拟头节点
|
||
impl Solution {
|
||
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
|
||
let mut dummy_head = Box::new(ListNode::new(0));
|
||
dummy_head.next = head;
|
||
let mut cur = dummy_head.as_mut();
|
||
while let Some(mut node) = cur.next.take() {
|
||
if let Some(mut next) = node.next.take() {
|
||
node.next = next.next.take();
|
||
next.next = Some(node);
|
||
cur.next = Some(next);
|
||
cur = cur.next.as_mut().unwrap().next.as_mut().unwrap();
|
||
} else {
|
||
cur.next = Some(node);
|
||
cur = cur.next.as_mut().unwrap();
|
||
}
|
||
}
|
||
dummy_head.next
|
||
}
|
||
}
|
||
```
|
||
|
||
```rust
|
||
// 递归
|
||
impl Solution {
|
||
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
|
||
if head.is_none() || head.as_ref().unwrap().next.is_none() {
|
||
return head;
|
||
}
|
||
|
||
let mut node = head.unwrap();
|
||
|
||
if let Some(mut next) = node.next.take() {
|
||
node.next = Solution::swap_pairs(next.next);
|
||
next.next = Some(node);
|
||
Some(next)
|
||
} else {
|
||
Some(node)
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### C#
|
||
```csharp
|
||
// 虚拟头结点
|
||
public ListNode SwapPairs(ListNode head)
|
||
{
|
||
var dummyHead = new ListNode();
|
||
dummyHead.next = head;
|
||
ListNode cur = dummyHead;
|
||
while (cur.next != null && cur.next.next != null)
|
||
{
|
||
ListNode tmp1 = cur.next;
|
||
ListNode tmp2 = cur.next.next.next;
|
||
|
||
cur.next = cur.next.next;
|
||
cur.next.next = tmp1;
|
||
cur.next.next.next = tmp2;
|
||
|
||
cur = cur.next.next;
|
||
}
|
||
return dummyHead.next;
|
||
}
|
||
```
|
||
``` C#
|
||
// 递归
|
||
public ListNode SwapPairs(ListNode head)
|
||
{
|
||
if (head == null || head.next == null) return head;
|
||
var cur = head.next;
|
||
head.next = SwapPairs(head.next.next);
|
||
cur.next = head;
|
||
return cur;
|
||
}
|
||
```
|
||
|