Problem: 24. 两两交换链表中的节点

题目描述

思路

1.创建虚拟头节点dummy和尾指针tial指向dummy；创建指针p指向head
2.当head不为空同时head -> next 不为空时：

2.1.创建指针nextP指向p -> next -> next;
2.2.tial指向p -> next同时将p -> next置空；tial指针后移、p -> next -> next置空
2.3.tail指向p，同时p->next置空，tail指针后移；将p指向nextp；
2.4.若链表的长度为奇数，则最后p不为空则p->next为空，则直接让tail指向p并返回dummy -> next;

复杂度

时间复杂度:

$O(n)$；其中$n$是链表的长度

空间复杂度:

$O(n)$

Code

/*** 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:/**** @param head The head node of linked list* @return ListNode**/ListNode* swapPairs(ListNode* head) {ListNode* dummy = new ListNode(INT_MIN);ListNode* tail = dummy;ListNode* p = head;while (p != nullptr && p -> next != nullptr) {ListNode* nextP = p -> next -> next;tail -> next = p -> next;tail = tail -> next;p -> next -> next = nullptr;tail -> next = p;p -> next = nullptr;tail = tail -> next;p = nextP;}//If the list length is odd, the last node is added to the resulting listif (p != nullptr) {tail -> next = p;}return dummy -> next;}
};