初始链表头节点为head,将链表两个相邻元素进行组队。若链表长度为奇数,则最后一个元素单独一组。例如一个链表:1->2->3->4->5,组队后为[1->2]->[3->4]->[5].交换相邻组位置,即第一组和第二组交换,第三和第四组交换,上面的链表就变成[3->4]->[1->2]->[5]
时间: 2023-05-29 16:06:35 浏览: 98
思路:使用三个指针,分别指向当前组的前一个节点、当前组的第一个节点、当前组的第二个节点。循环遍历链表,每次将当前组的两个节点交换位置,然后将三个指针向后移动两个节点,即指向下一个组的前一个节点、第一个节点、第二个节点。
代码实现:
```
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1); // 添加哨兵节点,简化边界情况的处理
dummy->next = head;
ListNode* pre = dummy; // 当前组的前一个节点
ListNode* cur = head; // 当前组的第一个节点
ListNode* nxt = head ? head->next : nullptr; // 当前组的第二个节点
while (nxt) {
ListNode* nxtGroup = nxt->next; // 下一个组的第一个节点
pre->next = nxt; // 将前一个组的后继节点指向当前组的第二个节点
nxt->next = cur; // 将当前组的第二个节点指向当前组的第一个节点
cur->next = nxtGroup; // 将当前组的第一个节点指向下一个组的第一个节点
pre = cur; // 三个指针向后移动两个节点
cur = nxtGroup;
nxt = nxtGroup ? nxtGroup->next : nullptr;
}
head = dummy->next;
delete dummy;
return head;
}
```
阅读全文