24. Swap Nodes in Pairs

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.

Solution:

We use a dummy node to avoid a corner case of the first node.

Go through the linked list, and flip the next node and the next.next node of the current one. And set the current one to its next.next.

For this kind of problems, we need to be careful that when we process a node, it is not null.



Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
    
        while (head.next != null && head.next.next != null) {
            ListNode first = head.next;
            ListNode second = head.next.next;
            first.next = second.next;
            second.next = first;
            head.next = second;
            
            head = head.next.next;
        }
        return dummy.next;
    }
}