24. Swap Nodes in Pairs

• Difficulty: Medium

• Topics: Linked List

• Similar Questions:

  • Reverse Nodes in k-Group

Problem:

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.

Solutions:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        while (head && head->next) {
            ListNode* first = head;
            ListNode* second = head->next;
            head = head->next->next; // remember to the head of next round intermidiately
            tail->next = second;
            second->next = first;
            tail = first;
            tail->next = nullptr;
        }

        if (head) {
            tail->next = head;
        }

        return dummyHead->next;
    }
};