题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
解题思路
交换链表中相邻节点的问题可以通过迭代或递归来解决。本文将介绍两种方法:
方法一:迭代法
- 使用一个虚拟头节点
dummy
,指向链表的实际头节点head
,这样可以简化头节点的处理。 - 使用指针
prev
指向需要交换节点的前一个节点,初始化为dummy
。 cur
指向当前要交换的两个节点中的第一个节点,第二个节点由cur->next
指向。- 交换
cur
和cur->next
中的两个节点,然后将指针前移,继续交换下一个一对节点直至链表末尾。
方法二:递归法
- 如果链表为空或者只有一个节点,直接返回头节点。
- 递归交换后续节点,并将当前节点与后续节点交换。
接下来是两种方法的具体实现。
算法实现
方法一:迭代法实现(C++实现)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* temp = dummyHead;
while (temp->next != nullptr && temp->next->next != nullptr) {
ListNode* node1 = temp->next;
ListNode* node2 = temp->next->next;
temp->next = node2;
node1->next = node2->next;
node2->next = node1;
temp = node1;
}
ListNode* ans = dummyHead->next;
delete dummyHead;
return ans;
}
};
方法二:递归法实现(C++实现)
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),其中n是链表的长度。每两个节点进行一次交换,总体需要遍历整个链表。
- 空间复杂度:O(1),只使用了有限的额外空间。
-
方法二:递归法
- 时间复杂度:O(n),每两个节点进行一次交换,总体需要遍历整个链表。
- 空间复杂度:O(n),因为使用了递归调用,递归调用栈的深度取决于链表的长度。
总结
通过本文,我们介绍了两种解决LeetCode24题目中两两交换链表节点的方法:迭代法和递归法。两种方法都能有效地解决问题,但其不同点在于实现的风格和空间复杂度。迭代方法使用常数空间,适用于不希望使用递归的场景。而递归方法实现较为简洁,但占用较多栈空间。在实际应用中,可以根据具体需求选择合适的方法来解决这个问题。
希望这篇博客能对你有所帮助。如果有任何问题,欢迎随时讨论。
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » LeetCode 24 - 两两交换链表中的节点
发表评论 取消回复