参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
《代码随想录》算法公开课:帮你把链表细节学清楚! | LeetCode:24. 两两交换链表中的节点,相信结合视频在看本篇题解,更有助于大家对链表的理解。
这道题目正常模拟就可以了。
建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。
对虚拟头结点的操作,还不熟悉的话,可以看这篇链表:听说用虚拟头节点会方便很多?。
接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序
初始时,cur指向虚拟头结点,然后进行如下三步:
操作之后,链表如下:
看这个可能就更直观一些了:
对应的C++代码实现如下: (注释中详细和如上图中的三步做对应)
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移动两位,准备下一轮交换
}
return dummyHead->next;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
这里还是说一下,大家不必太在意力扣上执行用时,打败多少多少用户,这个统计不准确的。
做题的时候自己能分析出来时间复杂度就可以了,至于力扣上执行用时,大概看一下就行。
上面的代码我第一次提交执行用时8ms,打败6.5%的用户,差点吓到我了。
心想应该没有更好的方法了吧,也就$O(n)$的时间复杂度,重复提交几次,这样了:
力扣上的统计如果两份代码是 100ms 和 300ms的耗时,其实是需要注意的。
如果一个是 4ms 一个是 12ms,看上去好像是一个打败了80%,一个打败了20%,其实是没有差别的。 只不过是力扣上统计的误差而已。
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;
}
//迭代版本
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:
// 递归版本
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;
}
}
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;
}
}
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:
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
}
// 递归版本
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:
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;
};
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:
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:
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:
// 虚拟头节点
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:
//虚拟头结点
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:
// 虚拟头节点
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
}
}
// 递归
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if head == None || head.as_ref().unwrap().next == 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)
}
}
}