本文最后更新于 2025-03-31T00:09:09+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1] 提示:
链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100
进阶:你能在不修改链表节点值的情况下解决这个问题吗?(也就是说,仅修改节点本身。)
|
题目思路
- 1、最简单的思路自然是递归的思路
- 2、而递归调用的也是栈的实现方法,所以自然也能想到栈的相应的做法。
代码块
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head == nullptr || head -> next == nullptr) return head; stack<ListNode* > stk; ListNode* p = new ListNode(); ListNode* pos = head; head = p; while(pos != nullptr && pos -> next != nullptr) { stk.push(pos); stk.push(pos -> next); pos = pos -> next -> next; p -> next = stk.top(); stk.pop(); p = p -> next; p -> next = stk.top(); stk.pop(); p = p -> next; } if(pos != nullptr) p -> next = pos; else p -> next = nullptr; return head -> next;
} };
|
复杂度
Day-08 24. 两两交换链表中的节点
https://chaggle.github.io/2021/09/17/Leetcode/91-day/day-08/