Problem Statement
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.Solution
- Lets look at the first two nodes first.
- We need to move head to second. (One time operation)
- Move next of First to next of Second
- Move next of Second to First
- All looks fine. We can go like this in pairs.
- Now, what about joining the pairs?
- We need another pointer who will be responsible of joining these pairs.
Code
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
ListNode t = this;
while (t != null) {
sb.append(t.val).append(" -> ");
t = t.next;
}
return sb.toString();
}
}
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode first = head;
ListNode second = head.next;
ListNode prev = null;
ListNode result = second;
while (first != null && second != null) {
first.next = second.next;
second.next = first;
if (prev != null) {
prev.next = second;
}
prev = first;
first = first.next;
if (first != null) {
second = first.next;
}
}
return result;
}Leet Code submission result
Runtime: 0 ms, faster than 100.00% of Java online submissions for Swap Nodes in Pairs. Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Swap Nodes in Pairs.
