每天一算：Swap Nodes in Pairs
16lz
2021-01-22
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上的算法题目，并给出该题目的动画解析以及参考答案，每篇文章阅读时长为五分钟左右。
更多相关文章
- 动画：面试算法之求二叉树的下一节点
- php+nodeJs+thrift协议，实现zookeeper节点数据自动发现
- 同样的复杂度，为什么插入排序比冒泡排序更受欢迎？
- 数据结构--时间复杂度与空间复杂度
- jQuery的DOM操作实例（3）——创建节点&&编写一个弹窗
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元
- 如何在java脚本中获取节点内部文本?
- Study JQuery《zTree自动点击第一个节点》