Swap Nodes in Pairs

---

Swap Nodes in Pairs: 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

---

Try this Problem on your own or check similar problems:

1. Swapping Nodes in a Linked List
2. Reverse Nodes in k-Group

Solution:

Java

public ListNode swapPairs(ListNode head) {
    if(head == null || head.next == null) return head;
    ListNode dummy = new ListNode(-1, head), iter = dummy.next, lastPairTail = dummy;

    while(iter != null && iter.next != null){
        lastPairTail.next = iter.next;
        iter.next = iter.next.next;
        lastPairTail.next.next = iter;
        lastPairTail = iter;
        iter = iter.next;
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  if (head === null || head.next === null) return head;
  const dummy = new ListNode(-1, head);
  let iter = dummy.next;
  let lastPairTail = dummy;

  while (iter !== null && iter.next !== null) {
    lastPairTail.next = iter.next;
    iter.next = iter.next.next;
    lastPairTail.next.next = iter;
    lastPairTail = iter;
    iter = iter.next;
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        dummy = ListNode(-1, head)
        iter = dummy.next
        lastPairTail = dummy

        while iter is not None and iter.next is not None:
            lastPairTail.next = iter.next
            iter.next = iter.next.next
            lastPairTail.next.next = iter
            lastPairTail = iter
            iter = iter.next

        return dummy.next

C++

/**
 * 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) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* dummy = new ListNode(-1, head);
        ListNode* iter = dummy->next;
        ListNode* lastPairTail = dummy;

        while (iter != nullptr && iter->next != nullptr) {
            lastPairTail->next = iter->next;
            iter->next = iter->next->next;
            lastPairTail->next->next = iter;
            lastPairTail = iter;
            iter = iter->next;
        }

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We change the connections next pointers of the nodes in pair by:

• first placing the second node to be the first node in the pair
• making the first node point to the first node in the next pair
• making the second node (now the first) point to the previous head (first node) of the pair
• setting the lastPairTail (the second/last element of previous pair) to point to the second element of the pair (initially the first node, before the swap)

We move the iter until there is no more pairs to swap iter.next == null.