2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ In gerenal you are right, but I don't see how that would actually help much in this case. You'd still want to do null checks and would have to pass in extra Nodes to the swapping method. \$\endgroup\$ – Imus Apr 9 '18 at 13:18
  • \$\begingroup\$ I thought of swapping the nodes in a separate methods but I wasn't sure of how many arguments to pass. \$\endgroup\$ – CodeYogi Apr 9 '18 at 15:48
  • \$\begingroup\$ @CodeYogi Only one parameter, see edit. \$\endgroup\$ – mtj Apr 10 '18 at 5:47
  • \$\begingroup\$ I don't think this is an improvement. It's not immediatly obvious what the pairSwapHeadwill return. Combined with still doing a lot off something.next or something.next.next things in the main method means it becomes harder to search for a possible bug. \$\endgroup\$ – Imus Apr 10 '18 at 7:59
  • \$\begingroup\$ @Imus Your opinion vs. my opinion. Let's not get into discussion here, and just accept it as an alternative approach. \$\endgroup\$ – mtj Apr 10 '18 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.