leetcode之hot100---24两两交换链表中的节点(C++)
思路一:迭代
首先引入虚拟头节点以简化链表操作,
然后使用指针逐步遍历链表,判断当前节点后是否存在可交换的相邻节点。
若存在,则通过调整节点之间的链接顺序,将相邻节点的位置互换,同时保持链表的整体结构。交换完成后,指针移动到下一对节点,重复上述过程,不断更新需要交换的键对中第一个节点的位置,直至链表遍历结束。最终返回更新后的链表头节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
//使用双指针遍历相邻节点,进行反转
//如果链表为空或链表中只有头节点一个元素,那么直接返回头节点
if(head == nullptr || head->next == nullptr){
return head;
}
//虚拟化一个哨兵节点,用于返回链表的头节点
ListNode* sentry = new ListNode(-1, head);
//初始化前驱节点和第一个需要交换的值对中的第一个节点
ListNode* pre = sentry;
ListNode* p1 = head;
//相邻节点反转
while(p1 && p1->next){
ListNode* p2 = p1->next;//需要交换的第二个节点
ListNode* nxt = p2->next;//下一个需要交换值对的起始节点
//交换两个值对
p1->next = p2->next;
p2->next = p1;
pre->next = p2;
//更新前驱节点和需要交换的第一个节点的位置
pre = p1;
p1 = nxt;
}
ListNode* ans = sentry->next;
delete sentry;
return ans;
}
};
交换键值对的图解:
0:初始值
1:p1->next = nxt;
2:p2->next = p1;
3:pre->next = p2;
4:pre = p1;
p1 = nxt;
-
时间复杂度:O(n)
-
空间复杂度:O(1)
思路二:递归
遍历链表,找到需要进行交换的键对,不断调用函数将其进行交换,最终返回头节点
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};
-
时间复杂度:O(n)
-
空间复杂度:O(n)