Description

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

 

Example 1:

 

Input: head = [1,2,3,4]

Output: [2,1,4,3]

 

Example 2:

Input: head = []

Output: []

 

Example 3:

Input: head = [1]

Output:[1]

 

Constraints:

• The number of nodes in the list is in the range [0, 100].

• 0 <= Node.val <= 100

Thinking

That's right, a linked list problem. Swapping part of the nodes is a popular type of questions in linked list. All we need to do is to figure out what information we need to get before each transition/swapping. In this problem, to swap a pair of nodes, we need to know the node before the pair, the pointer of the pair of nodes, and the head of the following nodes. That is 4 pointers! Then we just need to cover all the edge cases: if you want to access a pointer's next node, make sure this pointer is not nullptr, or have some measurement to deal with it.

My approach

​x
/**
 * 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) {
        // Edge case 1
        if(head == nullptr) return nullptr;
        
        ListNode dummy = ListNode(0, head);
        ListNode *first = head, *second = first->next;
        ListNode *nxt, *prev = &dummy;
        
        while(second) {
            nxt = second->next;

            prev->next = second;
            second->next = first;
            first->next = nxt;

            prev = first;
            first = nxt;
            
            // Edge case 2
            second = first == nullptr ? nullptr : first->next;
        }

        return dummy.next;
    }
};

To initialize the *prev pointer, we need to have a dummy head that is prior to the *head, this makes our operation intuitive and convenient.

• Edge case 1: Since I initialize *second as the first->next, I need to make sure first != nullptr.

• Edge case 2: To prepare for the next round's second, if first is nullptr, it means the list has ended. Just assign nullptr to second to stop the loop and to avoid accessing nullptr.

What I learned

1. Whenever you access the next pointer, thinking about if it is possible you access a nullptr.

2. Using dummy node.