题目描述
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
,接下来进行重复操作
代码如下:
1 | class Solution { |
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 24.SwapNodesInPairs.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions