Swap adjacent element in a linked list

While seeing a programming interview site, I came across code which swap adjacent elements in a linked list, but I found it to be a bit wrong. Below is the code.

void swap (struct list **list1)
{
    struct list *cur, *tmp, *next;
    cur = *list1;
    if (cur && cur->next)
        *list1 = cur->next;

    //To make sure that we have at least two more elements to be swapped.
    while (cur && cur->next)
    {
        next = cur->next;
        tmp = next->next;
        next->next = cur;
        //We have to make 1->next as 4 in above example (figure).

        if (tmp)
            cur->next = tmp->next;
        cur = tmp;
    }
    return;
}

Now for me, the condition if (temp) is not right here. Is that assessment correct?

Suppose we do have a linked list like:

  1->2->3->4->NULL

Now our objective is to make a开发者_如何学运维 linked list like:

2->1->4->3->NULL

My worry is if the if (temp) is there in our code, we can't assign null at end of the linked list.

You are right. This doesn't work. It creates a loop at the end of the list, and if you run swap twice on the same list, the second run will get into an endless loop.

To fix this awkward code, replace the if (tmp) with the following code:

if(tmp)
    if (tmp->next)
        cur->next = tmp->next;
    else
        cur->next = tmp;    // take care of an add number of nodes
else
    cur->next = NULL;   // take care of an even number of nodes

It will take care of the last nodes:

1. If there's an even number of nodes, it makes sure the last points to NULL instead of the node before it.
2. If there's an odd number of nodes, checking cur->next will prevent the following iteration, so the last node must be pointed by the one before it before the loop is exited.

It tests it to make sure it's not NULL (the last element). Not testing it will make your program follow the NULL pointer for the last element of the list.

tmp = next->next; /* If `next` is the last, `next->next` is NULL. */

Yes, you are right that there's a bug in the function - cur->next isn't updated correctly in all cases.

I personally find the local variable names tmp and next not particularly helpful and actively confusing in the case of next. Those names make it hard for me to keep track in my head of what's going on as I read through the function.

I find that the names node1, node2, and node3 work better to for me to keep a mental picture of which node is being manipulated. I wouldn't be surprised if other people disagree, though.

Here's a reworked version of the function that I find more readable, and more importantly that I believe is correct.

void swap (struct list **head)
{
    struct list *node1 = *head;
    struct list *node2 = node1 ? node1->next : NULL;

    // handle degenerate cases
    if (!node2) {
        // no elements or only one element on the list
        //  nothing to do...
        return;
    }    

    // fix-up list head to what will be the new first node on list
    *head = node2;        

    // while there are at least 2 more elements to be swapped
    while (node1 && node2) {
        struct list* node3 = node2->next;

        // get a pointer to the node that will be the remainder of the
        //  list after the remainder of the list is processed.  
        //
        // This will be NULL, node3, or 'node4' depending on whether 
        //  there are 0 , 1 or 2+ nodes following node1 and node2
        struct list* remainder = (node3 && node3->next) ? node3->next : node3;

        node1->next = remainder;
        node2->next = node1;

        // prepare pointers to the next two nodes to be swapped
        node1 = node3;
        node2 = node3 ? node3->next : NULL;
    }

    return;
}

Java Implementation

Given: 1->2->3->4->5->6

Logic 1. First - 1, Second - 2, Third 3
2. Second.next = first
3. First.next = Third.next depending on even or odd numbers update accordingly

public ListNode evenOddMerge(ListNode head) {

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

        ListNode first = head;
        ListNode second = first.next;
        ListNode third = null;

        head = second;

        while (true) {

            third = second.next;

            second.next = first;

            if (third == null || third.next == null) {
                first.next = third;
                break;
            }

            first.next = third.next;

            first = third;
            second = first.next;
        }

        return head;
    }

Credits: Geeks for Geeks