Swapping the odd and even position in a linked list

A simple and intuitive solution to the problem !! It might not be very efficient but it does certainly work.


node* swap(node *head)
{
    node dummy;
    node *prev, *curr, *u, *tmp;

    if (head==NULL) return head;

    prev=&dummy;
    for(curr=head; curr!=NULL && curr->next!=NULL; ) {
        u = curr->next;
        tmp = u->next;
        prev->next = u;
        u->next = curr;
        prev = curr;
        curr = tmp;
    }
    prev->next = curr;
    return dummy.next;
}

void print(const node *head)
{
    for(const node *p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}

Linked List Insert nth problem

A linked list problem for inserting a node after the nth index !!

InsertNth() Solution


void InsertNth(struct node** headRef, int index, int data)
if (index == 0)
   Push(headRef, data);                       // position 0 is a special case...
else {
  struct node* current = *headRef;
   int i;
     for (i=0; i<index-1; i++) {
     assert(current != NULL); // if this fails, index was too big
     current = current->next;
      }
Push(&(current->next), data);
}
}

Reverse a Linked List

This question is one of the most repeated ones across Google, Microsoft, Amazon and a few more. The thing which makes it a good question is that after you scratch your head and give them an algorithm they either ask you to optimize it for the boundary cases (which is fine for most of the candidates) or they ask you to do it the other way round.

I am going to give you both, recursive as well as an iterative solution. For both the techniques :

Initially call the method as : head = reverseList(head,NULL)


Iterative :

Node *Reverse (Node *p)
{
   Node *pr = NULL;
   while (p != NULL)
   {
      Node *tmp = p->next;
      p->next = pr;
      pr = p;
      p = tmp;
   }
   return pr;
}
-----------------------------------------------------------------------
Recursive:

Node *reverseList(Node *current, Node *parent)
{
        Node *revHead;
   if(current == null)
      revHead = parent;
   else
   {
      revHead = reverseList(current->next,current);
      current->next = parent;      
   }
   return revHead;
}

Acyclic Linked-List Detection Algorithm

Write a function that takes a pointer to the head of a list and determines whether the list is cyclic or acyclic. Your function should return false if the list is acyclic and true if it is cyclic. You may not modify the list in any way.

int determineTermination( node *head )
        { 
           node *fast, *slow;
           fast = slow = head; 
                  while( true )
                       {
                           if( !fast || !fast->next ) 
                              return false; 
                           else if( fast == slow || fast->next == slow ) 
                              return true; 
                           else 
                              {
                                 slow = slow->next; 
                                 fast = fast->next->next; 
                              }
                        }
        }


Leave your comments below the post.
Happy coding :)