LeetCode24. Swap Nodes in Pairs（链表 / 模拟）

LeetCode24. Swap Nodes in Pairs（链表）

• Medium
• Accepted：282,686
• Submissions：654,352

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

链接

https://leetcode.com/problems/swap-nodes-in-pairs

题意

给定一个链表，交换每两个相邻的结点，返回头结点。不允许修改链表的值。

题解

• 对于当前结点head和head指向的下一个结点head->next，将两个结点进行交换我们需要让head->next = head->next->next，然后让head->next->next = head，最后再让一个节点指向之前的head->next，所以我们需要增加一个虚拟头结点以及保存交换结点的信息。

• 具体交换操作就是pre->next=node2 node2->next=node1 mode1->next=next，完成交换后，我们再让pre=node1更新信息。
• 时间复杂度$O(n)$。

代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Swap Nodes in Pairs.
• Memory Usage: 9 MB, less than 32.89% of C++ online submissions for Swap Nodes in Pairs.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
         ListNode* virtualHead = new ListNode(0);
         virtualHead->next = head;
         ListNode* pre = virtualHead;
         while (pre->next && pre->next->next)
         {
             ListNode* node1 = pre->next;
             ListNode* node2 = node1->next;
             ListNode* next = node2->next;

             // 交换
             node2->next = node1;
             node1->next = next;
             pre->next = node2;

             pre = node1; // 下一次交换
         }
         ListNode* retNode = virtualHead->next;
         delete virtualHead;
         return retNode;
    }
};

• Runtime: 3 ms, faster than 69.99% of C++ online submissions for Swap Nodes in Pairs.
• Memory Usage: 7.6 MB, less than 54.77% of C++ online submissions for Swap Nodes in Pairs.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        
        // 虚拟头节点
        ListNode* cur = dummyNode;
        while (cur->next != NULL && cur->next->next != NULL)
        {
            // 临时节点
            ListNode* nextNode = cur->next;
            ListNode* nextNextNode = cur->next->next->next;
            
            // 注意，从第一个开始就已经更新了
            cur->next = cur->next->next;
            cur->next->next = nextNode;
            cur->next->next->next= nextNextNode;
            
            // 往后移动
            cur = cur->next->next;
        }
        
        // 删除虚拟头结点
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};