题目描述
Given a linked list, swap every two adjacent nodes and return its head.
Example 1:
Input: head = [1,2,3,4] Output: [2,1,4,3]
Example 2:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100
迭代版本解题思路
- 生成一个伪的头节点，并让一个指针指向这个伪的头节点
- 需要以下几步操作
- 伪的头结点的下一个节点指向head
- 保存head -> next -> next (便于下一个循环)
- 然后tail -> next = head -> next;
- head -> next -> next = head;
- tail = head;
- tail -> next = nextptr; //这一步非常重要，将调整完的节点串联起来
- head = nextptr; // 进行下一步循环
/**
* 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){
return head;
}
ListNode* dummy = new ListNode(-1);
ListNode* tail = dummy;
tail -> next = head;
while(head && head -> next){
ListNode* nextptr = head -> next -> next;
tail -> next = head -> next;
head -> next -> next = head;
tail = head;
tail -> next = nextptr;
head = nextptr;
}
head = dummy -> next;
delete dummy;
return head;
}
};
