Swap Nodes in Pairs in singly linked list

Question

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 && 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

Answer 1

The general "algorithm" looks pretty decent already. The only minor issue is, as you mentioned yourself, that you are creating extra variables just to give them different names.

If you restructure it a little bit I think it's readable enough without those.

It helps if you start with updating the "prev" at the beginning of the loop. I mean both setting the prev.next to the current.next and then updating the prev value to what will become the new second ListNode. That way we know that part is handled entirely and we don't need to keep a mental note to fix it anymore.

After that you only need to actually swap the 2 nodes and setup the current one for the next iteration. When I first rewrote this my IDE started to complain that the current variable is redundant as well. You can just use the input parameter for that.

The result looks like this:

public static ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode result = head.next;

    ListNode prev = null;
    while (head != null && head.next != null) {
        if (prev != null) {
            prev.next = head.next;
        }
        //head will become the first after swap
        prev = head;

        //the actual swap
        ListNode temp = head.next;
        head.next = temp.next;
        temp.next = head;

        //head is the second one after the swap. Take the next of that one for the new head in the next iteration
        head = head.next;
    }

    return result;
}

I have renamed newHead to result to make it even more obvious that this is what we will be returning at the end of the method. You don't really need to do this.

I put in the comments to help you read the code. Normally I wouldn't include those in production code.

---

Bonus: There is a way to re-use the prev variable instead of creating a new temp. This is fun to do if you don't ever want anyone to understand your code anymore. Please don't optimise like this in actual production code:

public static ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode result = head.next;
    ListNode temp = null;
    while (head != null && head.next != null) {
        if (temp != null) {
            temp.next = head.next;
        }
        temp = head;
        head = head.next;

        temp.next = head.next;
        head.next = temp;

        head = temp.next;
    }
    return result;
}

Answer 2

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 <T> ListNode<T> pairSwapHead(ListNode<T> head) {
    if(head == null || head.succ == null)
        return head;
    ListNode<T> next = head.succ;
    head.succ = next.succ;
    next.succ = head;
    return next;
}

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

    while(curr != null && 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<T> 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;
}