每天一算:Swap Nodes in Pairs

每天一算:Swap Nodes in Pairs

LeetCode上第24号问题:Swap Nodes in Pairs

题目

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

  • 你的算法只能使用常数的额外空间。    

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

解题思路

该题属于基本的链表操作题。

  • 设置一个虚拟头结点dummyHead

  • 设置需要交换的两个节点分别为node1node2,同时设置node2的下一个节点next

在这一轮操作中
  • node2节点的next设置为node1节点

  • node1节点的next设置为next节点

  • dummyHead节点的next设置为node2

  • 结束本轮操作

接下来的每轮操作都按照上述进行。

动画演示

动画演示GIF有点大,请稍微等待一下加载显示^_^

每天一算:Swap Nodes in Pairs

参考代码

 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};

执行结果

每天一算:Swap Nodes in Pairs

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

每天一算:Swap Nodes in Pairs
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Swap Nodes in Pairs

我还会在以下平台发布内容

GitHub 哔哩哔哩