CODEWITHSUNDEEP
algorithmdata-structures
Vallabh Patade
Vallabh Patade

Reputation: 5110

swapping adjacent nodes of a LinkedList

I have to swap two adjacent node(not their data) in a linked list. e.g. 1) Input a->b->c->d->e->f, Output : b->a->d->c->f->e 2) Input a->b->c->d->e, Output : b->a->d->c->e

I have writen the following code is there any more efficient way (maybe with two temporary pointers) or simple logic?

node* swap(node* head) {
   node *first = head;
   node *second,*third,*result;

   if(head == NULL || head->next == NULL) {
        return head;
   }

    result = second = first->next;
    third = second->next;

    while(second != NULL) {
       second->next=first;
       first->next=(third->next==NULL ? third : third->next);
       first=third;
       second=(third->next==NULL ? third : third->next);
       third=(second==NULL ? second : second->next);
    }
    return result;
}

Upvotes: 5

Views: 9505

Answers (5)

Alex Hawkins
Alex Hawkins

Reputation: 604

In JavaScript

LinkedList.prototype.swapPairs = function() {
    var recurse = function(current) {
        if (!current) return this;
        if (current.next) {
            var save = current.next.value;
            current.next.value = current.value;
            current.value = save;
            current = current.next;
        }
        return recurse(current.next);
    }.bind(this);
    return recurse(this.head);
}

Upvotes: 1

Frank
Frank

Reputation: 1

Alex DiCarlo's recursion method is simpler but needs to be corrected slightly.

void swapEveryTwo(node* prev, node* node) {
    if (node != null && node->next != null) {
        swapTwo(prev, node, node->next);
        swapEveryTwo(node, node->next);
    }
}

Please correct me if I am wrong.

Thanks!

Upvotes: 0

Alex DiCarlo
Alex DiCarlo

Reputation: 4891

You can do this fairly simply with a recursion:

// Swaps node b and c.
void swapTwo(node* a, node* b, node* c) {
   if (a != NULL)
       a->next = c;
   b->next = c->next;
   c->next = b;
}

void swapEveryTwo(node* prev, node* node) {
    if (node != null && node->next != null) {
        swapTwo(prev, node, node->next);
        swapEveryTwo(node->next, node->next->next);
    }
}

Every call of swapEveryTwo swaps pairs of nodes, and then sets up the recursion for the next pair. Also, because this function is tail recursive, the compiler will undoubtedly optimize it to a while loop, ensuring no extra stack frames are allocated, and thus will be optimal. If you need further explanation, feel free to ask.

Edited to add swap function as in original post:

node* swap(node *head) {
    if (head != NULL && head->next != NULL) {
        node *newHead = head->next;
        swapEveryTwo(NULL, head);
        return newHead;
    } else {
        return head;
    }
}

Upvotes: 3

Gene
Gene

Reputation: 46990

Your algorithm is about the best possible. Often we can get a bit of speed through simplicity. Instead of drawing pictures and reasoning about pointers, think of popping elements off the head of the input list and using a queue add-to-tail operation to build up the result. In pseudocode, we have

set_empty(rtn);
while (head) {
   fst = pop(head);
   if (head) {
     snd = pop(head);
     add_at_tail(rtn, snd);
   }
   add_at_tail(rtn, fst);
}

The if is needed only to protect against the case where the input list has odd length. If we're sure the list is even in length, we can skip it.

Now pop is very easy to implement. The add-to-tail operation is easiest if we use a dummy head node. So in C, we have:

node *swap(node *head)
{
  node dummy[1];         // set_empty(rtn);
  node *rtn = dummy;
  while (head) {
    node *fst = head;    // fst = pop(head);
    head = head->next;
    if (head) {
      node *snd = head;  // snd = pop(head);
      head = head->next;
      rtn->next = snd;   // add_to_tail(rtn, snd);
      rtn = rtn->next;
    }
    rtn->next = fst;     // add_to_tail(rtn, fst);
    rtn = rtn->next;
  }
  rtn->next = NULL;      // terminate tail
  return dummy->next;
}

Now I have not tested this code, but I'm pretty sure it will run fine modulo maybe a typo or two. There are fewer tests than yours (just one per element). Tests are comparatively expensive because they can interfere with pipelining, so mine ought to run just a tad faster. Almost certainly this difference is irrelevant.

However, I think my code rather simpler to understand. Of course that's just one biased opinion, but readability does count during maintenance.

NB Now I have done a quick test and it worked on the first try! On the other hand when I tried your code I got a segv at 

 first->next=(third->next==NULL ? third : third->next);

Below is the test frame. Do you see anything wrong?

typedef struct node_s {
  struct node_s *next;
  int val;
} node;

// swap goes here

int main(void)
{
  node dummy[1];
  node *p = dummy;

  for (int i = 0; i < 16; i++) {
    p->next = malloc(sizeof(node));
    p = p->next;
    p->next = NULL;
    p->val = 'a' + i;
  }
  p = swap(dummy->next);
  while (p) {
    printf("%c ", p->val);
    p = p->next;
  }
  printf("\n");
  return 0;
}

Upvotes: 2

Spundun
Spundun

Reputation: 4034

Looks good. I added one correctness check (third==NULL) and removed one redundant expression. You are going through the whole list only once, which you have to do. So I think we can be pretty certain that this is the fastest way to do it.

node* swap(node* head) {
   node *first = head;
   node *second,*third,*result;

   if(head == NULL || head->next == NULL) {
        return head;
   }

    result = second = first->next;
    third = second->next;

    while(second != NULL) {
       second->next=first;
       second = first->next=((third==NULL || third->next==NULL) ? third : third->next);
       first=third;
       third=(second==NULL ? second : second->next);
    }
    return result;
}

Upvotes: 3

Related Questions