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; } }
|