swapping adjacent nodes of a LinkedList

Question

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

Answer 1

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

Answer 2

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

Answer 3

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