CODEWITHSUNDEEP
clinked-list
Amit Singh Tomar
Amit Singh Tomar

Reputation: 8610

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.

Upvotes: 3

Views: 1537

Answers (4)

Rohit
Rohit

Reputation: 6613

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

Upvotes: 0

Michael Burr
Michael Burr

Reputation: 340188

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;
}

Upvotes: 2

Eran
Eran

Reputation: 22020

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.

Upvotes: 4

cnicutar
cnicutar

Reputation: 182619

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. */

Upvotes: 2

Related Questions