每天一算：Swap Nodes in Pairs
LeetCode上第24号问题：Swap Nodes in Pairs
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 说明:
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解题思路
该题属于基本的链表操作题。
- 设置一个虚拟头结点
dummyHead - 设置需要交换的两个节点分别为
node1、node2，同时设置node2的下一个节点next
在这一轮操作中
- 将
node2节点的next设置为node1节点 - 将
node1节点的next设置为next节点 - 将
dummyHead节点的next设置为node2 - 结束本轮操作
接下来的每轮操作都按照上述进行。
动画演示
动画演示GIF有点大，请稍微等待一下加载显示^_^
参考代码
1// 24. Swap Nodes in Pairs
2// https://leetcode.com/problems/swap-nodes-in-pairs/description/
3// 时间复杂度: O(n)
4// 空间复杂度: O(1)
5class Solution {
6public:
7 ListNode* swapPairs(ListNode* head) {
8
9 ListNode* dummyHead = new ListNode(0);
10 dummyHead->next = head;
11
12 ListNode* p = dummyHead;
13 while(p->next && p->next->next){
14 ListNode* node1 = p->next;
15 ListNode* node2 = node1->next;
16 ListNode* next = node2->next;
17 node2->next = node1;
18 node1->next = next;
19 p->next = node2;
20 p = node1;
21 }
22
23 ListNode* retHead = dummyHead->next;
24 delete dummyHead;
25
26 return retHead;
27 }
28};执行结果
我们会在每天早上8点30分准时推送一条LeetCode上的算法题目，并给出该题目的动画解析以及参考答案，每篇文章阅读时长为五分钟左右。
举报
腾讯云开发者
