[LeetCode] 24. Swap Nodes in Pairs

Posted on | In

Problem

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:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.

Explanation

  1. From the problem example, we need to swap $1$ and $2$, then swap $3$ and $4$. In order to swap $3$ and $4$, we need a pointer that can point both node. In this case, to swap $3$ and $4$, we need a pre-node pointing at $2$, this pre-node can represent $3$ using pre.next and represent $4$ using pre.next.next. So, in order to swap the first two elements, we need to create a dummy node in front of the input’s head.

  2. Now, the node become this: pre->1->2->3->4. The solution basically do:

    1
    2
    3
     pre->2->3->4
 1->3->4
 pre->2->1->3->4

  3. After we swap, we move the pre pointing to pre.next.next and repeat the above process.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        
        while(pre.next != null && pre.next.next != null) {
            ListNode temp = pre.next;
            pre.next = temp.next;
            temp.next = temp.next.next;
            pre.next.next = temp;
            
            pre = pre.next.next;
        }
        return res.next;
    }
}