2
LeetCode 第 24 号问题：两两交换链表中的节点
source link: https://www.cxyxiaowu.com/6859.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 24 号问题：两两交换链表中的节点-程序员小吴
当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 24 号问题：两两交换链表中的节点
本文首发于公众号「五分钟学算法」，是图解 LeetCode 系列文章之一。
题目来源于 LeetCode 上第 24 号问题：两两交换链表中的节点。题目难度为 Medium，目前通过率为 45.8% 。
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
该题属于基本的链表操作题。
- 设置一个虚拟头结点
dummyHead - 设置需要交换的两个节点分别为
node1、node2，同时设置node2的下一个节点next
在这一轮操作中
- 将
node2节点的next设置为node1节点 - 将
node1节点的next设置为next节点 - 将
dummyHead节点的next设置为node2 - 结束本轮操作
接下来的每轮操作都按照上述进行。
// 24. Swap Nodes in Pairs
// https://leetcode.com/problems/swap-nodes-in-pairs/description/
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* p = dummyHead;
while(p->next && p->next->next){
ListNode* node1 = p->next;
ListNode* node2 = node1->next;
ListNode* next = node2->next;
node2->next = node1;
node1->next = next;
p->next = node2;
p = node1;
}
ListNode* retHead = dummyHead->next;
delete dummyHead;
return retHead;
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK