daily leetcode - swap-nodes-in-pairs - !
题目地址
https://leetcode.com/problems/swap-nodes-in-pairs/
题目描述
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
思路
这道题不算难,是基本的链表操作题,我们可以分别用递归和迭代来实现。对于迭代实现,还是需要建立 dummy 节点,注意在连接节点的时候,最好画个图,以免把自己搞晕了.
思路2
设置一个dummy 节点简化操作,dummy next 指向head。
- 初始化first为第一个节点
- 初始化second为第二个节点
- 初始化current为dummy
- first.next = second.next
- second.next = first
- current.next = second
- current 移动两格
- 重复
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
关键点解析
-
链表这种数据结构的特点和使用
-
dummyHead简化操作
代码
解法一:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
dummy->next = head;
while (pre->next && pre->next->next) {
ListNode *t = pre->next->next;
pre->next->next = t->next;
t->next = pre->next;
pre->next = t;
pre = t->next;
}
return dummy->next;
}
};
递归的写法就更简洁了,实际上利用了回溯的思想,递归遍历到链表末尾,然后先交换末尾两个,然后依次往前交换:
解法二:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode *t = head->next;
head->next = swapPairs(head->next->next);
t->next = head;
return t;
}
};
代码2
- 语言支持:JS,Python3
/*
* @lc app=leetcode id=24 lang=javascript
*
* [24] Swap Nodes in Pairs
*
* https://leetcode.com/problems/swap-nodes-in-pairs/description/
*
* algorithms
* Medium (43.33%)
* Total Accepted: 287.2K
* Total Submissions: 661.3K
* Testcase Example: '[1,2,3,4]'
*
* Given a linked list, swap every two adjacent nodes and return its head.
*
* You may not modify the values in the list's nodes, only nodes itself may be
* changed.
*
*
*
* Example:
*
*
* Given 1->2->3->4, you should return the list as 2->1->4->3.
*
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
const dummy = new ListNode(0);
dummy.next = head;
let current = dummy;
while (current.next != null && current.next.next != null) {
// 初始化双指针
const first = current.next;
const second = current.next.next;
// 更新双指针和current指针
first.next = second.next;
second.next = first;
current.next = second;
// 更新指针
current = current.next.next;
}
return dummy.next;
};
Python3 Code:
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
"""
用递归实现链表相邻互换:
第一个节点的next是第三、第四个节点交换的结果,第二个节点的next是第一个节点;
第三个节点的next是第五、第六个节点交换的结果,第四个节点的next是第三个节点;
以此类推
:param ListNode head
:return ListNode
"""
# 如果为None或next为None,则直接返回
if not head or not head.next:
return head
_next = head.next
head.next = self.swapPairs(_next.next)
_next.next = head
return _next
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode
daily leetcode - swap-nodes-in-pairs - !
本博客所有文章除特别声明外,均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来自 Hi I'm LouisLan!
评论
0 评论