题目描述
Given a linked list, swap every two adjacent nodes and return its head.
例子
例子 1
Input:
head = [1,2,3,4]
Output:[2,1,4,3]
例子 2
Input:
head = []
Output:[]
例子 3
Input:
head = [1]
Output:[1]
Follow Up
Can you solve the problem without modifying the values in the list’s nodes? (i.e., Only nodes themselves may be changed.)
Constraints
- The number of nodes in the list is in the range
[0, 100]
.0 <= Node.val <= 100
解题思路
这道题的关键是搞清楚要交换的节点,以两个节点为一个单元进行调整,假设目前要调整的单元为: prev->A->B->next
,其中 prev
及之前的调整已经完成,next
之后的调整还没开始。我们要做的是将其调整为 prev->B->A->next
,再对 next
和 next->next
进行同样操作。而在这中间我们要进行的步骤是:
- 将
prev
指向B
(A
需要备份),链表变成prev->B->next->... , A->B->next->...
- 此时
A
之后的链表的顺序仍未被改变,将A
指向A->next->next
(也就是B->next
),此时链表变成prev->B->next->..., A->next->...
- 将
prev->next
(B
) 指向A
,此时链表已经转换好,prev->B->A->next->...
- 将
A
设为A->next
,prev
设为prev->next->next
,接下来进行重复操作
代码如下:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* new_head = head->next;
ListNode* dummy = new ListNode();
ListNode* curr = head;
ListNode* prev = dummy;
while (curr && curr->next) {
prev->next = curr->next;
curr->next = curr->next->next;
prev->next->next = curr;
curr = prev->next->next->next;
prev = prev->next->next;
}
return new_head;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 24.SwapNodesInPairs.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions