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

For example, given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Iterative Solution, O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode first, second;

while (prev.next != null && prev.next.next != null){
first = prev.next;
second = prev.next.next;
first.next = second.next;
prev.next = second;
second.next = first;
prev = prev.next.next;
}

return dummy.next;
}
}

Recursive Solution, O(n) time O(n) space

1
2
3
4
5
6
7
8
9
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode second = head.next;
head.next = swapPairs(head.next.next);
second.next = head;
return second;
}
}