0%

[Leetcode]24. Swap Nodes in Pairs(C++)

题目描述

题目链接:24. Swap Nodes in Pairs

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,再对 nextnext->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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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