/**
* 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 h;
h.next = head;
for(ListNode *p = &h;p != nullptr && p->next != nullptr && p->next->next != nullptr;){
ListNode *p1 = p->next,*p2 = p1->next,*p3 = p2->next;
p->next = p2;
p1->next = p2->next;
p2->next = p1;
p = p1;
}
return h.next;
}
};
链表的两两交换可以在一次遍历中实现。
操作顺序如图所示。
需要注意其中的更改顺序。此更改顺序最优。
其他更改顺序可能会导致信息覆盖,因此可能需要存储额外的节点信息。
题目链接
原创不易,感谢支持!