24 两两交换链表中的节点
解答几个问题
- 为什么cur取 待交换元素的前一个位置
- 因为交换之后,还要保持链表相连,cur取上一次交换后的末尾位置,能够保证链表相连
/**
* 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) {
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode* cur = dummyNode;
while(cur->next != nullptr && cur->next->next != nullptr){
ListNode* tmp1 = cur->next;
ListNode* tmp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp1;
cur->next->next->next = tmp2;
cur = cur->next->next;
}
delete dummyNode;
return dummyNode->next;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)