LeetCode题目24：两两交换链表中的节点
原题描述
+
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
注意：你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例
输入：1->2->3->4
输出：2->1->4->3原题链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
思路解析
+
这道题用到的指针数量比较多，很一不小心容易乱。关键点在于两个节点交换之后，一定要能够和后面未操作的部分再度连起来，这就需要记住四个位置。
- 第一个要交换的节点位置（靠前），用first指针指代；
- 第二个要交换的节点位置（靠后），用second指针指代；
- 处于second后部，未被操作的子链表头位置，用head指代；
- 处于first前部子链表尾部位置，用prev指代。
然后，你才可以操作指针，形成prev->second->first->head的结构，如下图所示。
为了便于操作，代码中还是要加一个哑结点。
复杂度分析
+
- 时间复杂度：
- 空间复杂度：
C++参考代码
+
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *p = dummy, *first, *second;
while (head && head->next) {
first = head;
second = head->next;
head = second->next;
p->next = second;
second->next = first;
first->next = head;
p = p->next->next;
}
return dummy->next;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
