Swap Nodes in Pairs in singly linked list Description:

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.

Code:

class Solution {
    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode current = head;
        ListNode prev = null;
        ListNode newHead = head.next;

        while (current != null &amp;&amp; current.next != null) {

            ListNode first  = current;
            ListNode second = current.next;

            first.next = second.next;
            second.next = first;

            // check if its not the first pair
            if (prev != null) {
                prev.next = second;
            }

            // update pointers
            current = second;
            prev = current.next;
            current = current.next.next;
        }
        return newHead;
    }
}


Questions:

The above code passes all tests, the main struggle was the swapping logic and only after I chose meaningful names first and second I was able to clear my thoughts and move forward. Again I see that the linked list involves a lot of edge cases specially managing pointers.

I would like to know if there are some good to know points to avoid common mistakes in linked lists.

PS: Other feedbacks are welcomed too
Once again, splitting this into different parts would benefit the solution. Basically:


A method, which swaps the first two elements in a given list if there are at least two elements. Then return the new first element. (Just return the one element if there is only one.)
A method which iterates: call the first method on the list head, then advance the current pointer twice, then call the method again and update the next pointer of the current node. Repeat until finished.


In general: always try to split a problem into parts which you can tackle separately.



Due to the comments below, I feel compelled to break my personal rule of not just posting code. Thus, here's a working (not thorougly tested) approach which uses the idea presented above. I hope that makes it clearer. (Note: succ == successor, that is the naming I learned at scool a long time ago...)

private static &lt;T&gt; ListNode&lt;T&gt; pairSwapHead(ListNode&lt;T&gt; head) {
    if(head == null || head.succ == null)
        return head;
    ListNode&lt;T&gt; next = head.succ;
    head.succ = next.succ;
    next.succ = head;
    return next;
}

private static &lt;T&gt; ListNode&lt;T&gt; pairSwapList(ListNode&lt;T&gt; head) {
    ListNode&lt;T&gt; curr = pairSwapHead(head);
    ListNode&lt;T&gt; res = curr; // result of first swap is new head == return value

    while(curr != null &amp;&amp; curr.succ != null) {
        // second node of the current pair, which needs the next pointer
        // adjusted after the sublist starting at offset 2 gets swapped
        ListNode&lt;T&gt; needsNewNext = curr.succ;
        curr = curr.succ.succ;     // advance to sublist at offset two
        curr = pairSwapHead(curr); // swap first two elements
        needsNewNext.succ = curr;  // and adjust the pointer
    }
    return res;
}