力扣24. 两两交换链表中的节点

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 list
        if (p != nullptr) {
            tail -> next = p;
        }
        return dummy -> next;
    }
};