Reference: LeetCode
Difficulty: Medium

Problem

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

Note: 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.

Analysis

Test Case:

1
2
3
4
5
6
7
8
9
10
11
12
// 1
[1]
[1]
// 2
[1,2]
[2,1]
// 3
[1,2,3]
[2,1,3]
// 4
[1,2,3,4]
[2,1,4,3]

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode swapPairs(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  // prev -> head -> t -> nextTemp
  // prev -> t -> head -> nextTemp
  ListNode t = head.next;
  ListNode nextTemp = head.next.next;  // head.next is not null
  head.next = swapPairs(nextTemp);
  t.next = head;
  return t;
}

Time: $O(N)$
Space: $O(N)$

Iteration

Note: Use this template for most iterative methods:

1
2
3
4
5
6
7
8
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = head; // or use curr
ListNode prev = dummy; // act as a sentinel
while (p != null) { // p != null or p.next != null
  // ...
}
return dummy.next;

If I use p.next as a left-value in the block code, I have to indicate in the while condition that p.next != null. And usually, p != null and p.next != null are together.

Update prev before updating p.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode swapPairs(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode dummy = new ListNode(0); // since head might be swapped
  ListNode prev = dummy;
  ListNode p = head;
  // dummy -> 1 -> 2 ->   3    ->    4
  // prev     p    t  nextTemp
  // prev     t    p
  while (p != null && p.next != null) { // p.next is not necessary since each time move by 2 steps
    ListNode t = p.next;
    ListNode nextTemp = p.next.next;
    prev.next = t;
    t.next = p;
    p.next = nextTemp;
    // update
    prev = p;
    p = nextTemp;
  }
  return dummy.next;
}

Time: $O(N)$
Space: $O(1)$