24. 两两交换链表中的节点#

题目#

1
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
2

3
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
4

5
示例 1：
6

7
输入：head = [1,2,3,4]
8
输出：[2,1,4,3]
9

10
示例 2：
11

12
输入：head = []
13
输出：[]
14

15
示例 3：
16

17
输入：head = [1]
18
输出：[1]
19

20
提示：
21

22
链表中节点的数目在范围 [0, 100] 内
23
0 <= Node.val <= 100
24

25

26
进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

题目思路#

最简单的思路自然是递归的思路；
而递归调用的也是栈的实现方法，所以自然也能想到用栈来做的解法。

题目代码#

代码块#

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* swapPairs(ListNode* head) {
14
    if(head == nullptr || head -> next == nullptr) return head;
15
    stack<ListNode* > stk;
16
    ListNode* p = new ListNode();
17
    ListNode* pos = head;
18
        head = p;
19
    while(pos != nullptr && pos -> next != nullptr)
20
        {
21
      stk.push(pos);
22
      stk.push(pos -> next);
23
      pos = pos -> next -> next;
24
      p -> next = stk.top();
25
            stk.pop();
26
      p = p -> next;
27
      p -> next = stk.top();
28
            stk.pop();
29
      p = p -> next;
30
    }
31
    if(pos != nullptr) p -> next = pos;
32
      else p -> next = nullptr;
33
    return head -> next;
34
    /*
35
    if (head == nullptr || head->next == nullptr) return head;
36
        ListNode* p = head -> next;
37
        head -> next = swapPairs(p -> next);
38
        p -> next = head;
39
        return p;
40
    */
41
    }
42
};

复杂度#

时间复杂度：O(n)
空间复杂度：O(n)