Task

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

1

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

Solution

  • 使用dummy head在第一次交换时即得到“当前交换的两个节点”左右两侧都有节点的状态
  • 每次交换之初，确保两点：
    • 一个prev指针指向“当前交换的两个节点”左侧的节点
    • 一个head指针指向第一个要被交换的节点
  • 操作的时候：
    • 先交换节点之间的指针
    • 再更新prev和head的指向
  • 时间复杂度：只遍历一次，O(n)
  • 空间复杂度：只新建了一个dummy节点和2个指针，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Runtime: 4 ms, faster than 48.23% of C++ online submissions for Swap Nodes in Pairs.
// Memory Usage: 7.5 MB, less than 100.00% of C++ online submissions for Swap Nodes in Pairs.
/**
 * 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) {
        //新建dummy节点，使其next指向输入链表
        ListNode *dummy=new ListNode(0,head);
        ListNode *prev=dummy;
        while(head && (head->next)){
            //交换节点之间的指针
            prev->next=head->next;
            head->next=prev->next->next;
            prev->next->next=head;
            //更新prev和head的指向
            prev=head;
            head=head->next;
        }
        return dummy->next;
    }
};