Interview Coding Questions - Linked List

Linked List Data Structure

struct Node;

typedef struct Node *PtrToNode;

typedef PtrToNode List;

typedef PtrToNode Positon

struct Node

{

ElementType Element;

Position Next;

}

  
Algorithm 1 - Reverse a linked list (iterative implementation)   

  

    1     List   Reverse(List   l)   {   

    2     if(!l)   return   l;   

    3     list   cur   =   l.next;   

    4     list   pre   =   l;   

    5     list   tmp;   

    6     pre.next   =   null;   

    7     while   (   cur   )   {   

    8         tmp   =   cur;   

    9         cur   =   cur.next;   

  10         tmp.next   =   pre   

  11         pre   =   tmp;   

  12     }   

  13     return   tmp;   

  14   }   

Algorithm 2 - Reverse a linked list (recursive implementation)   

  1     List   Reverse(list   l)   {   

  2     if(!l   ||   !l.next)   return   l;   

  3       

  4         List   n   =   reverse(l.next);   

  5         l.next.next   =   l;   

  6         l.next=null;   

  7     }   

  8     return   n;   

  9   }