DS-LinkedList

Linked List

Node1->Node2->Node3.. ->Nodek->NULL.

Node:

-----------

|data|next|

-----------

Create Node of Linked List

struct Node { int data; struct Node *next; };

struct Node *createNode(int data)

{ struct Node *newnode=(struct Node*) malloc(sizeof(struct Node));

   newnode->next=NULL; newnode->data=data;

   return newnode;

}

Calculate if linked list length is odd or even

Use 2-x pointer.For odd linked list, it will be NULL, for even linked list, it will be non-null.

struct node* ptr2x=head;

while(ptr2x && ptr2x->next)

{    ptr2x=ptr2x->next->next;  }

if(ptr2x==NULL) ODD, else EVEN.

Find nth node from end

Smart and Efficient Way:

• Keep two pointers, p_nth, p_tmp. 
• Move p_tmp n times forward (as long as p_tmp is not NULL
• Now move p_tmp and p_nth together till p_tmp is NULL

struct node *NthFromEnd(struct node *head, int n)

struct node*p_nth, *p_tmp=head;

for(int i=0;i<n;i++)  if(p_tmp) p_tmp=p_tmp->next;

while(p_tmp)

{ if(p_tmp==NULL) p_nth=NULL

   else p_nth=p_nth->next;

}

if(p_nth) return p_nth.

return NULL;

Print Reverse LL

void PrintRev(struct node *head)

{ if(head=NULL) return;

   PrintRev(head->next);

   printf("%d->" head->data);

}

Reverse Linked List

void reverseLL(struct Node **head) //3-ptr

{

  struct Node *previous=NULL, *current=*head, *next;

  while(current){  next=current->next; current->next=previous; previous=current; current=next;   }

  *head=previous;

}

struct node *reverseLL(struct node *head) //2-ptr, head does current role

{ struct node *tmp=NULL, *next=NULL;

   while(head){ next=head->next;  head->next=tmp;  tmp=head;  head=next; }

   return tmp;

}

struct node* reverseLL_recursive(struct node *head)

{  if(head==NULL) return NULL;

    if(head->next==NULL) return head;

    struct node *second=head->next;   head->next=NULL; //Take head and cut from rest list

    struct node *rev_remaining=reverseLL_recursive(second);

    second->next=head; //join two lists

    return rev_remaining;

}

Rearrange LL inplace, N1->N2->N3->N3->...Nk  => N1->Nk->N2->Nk-1...

Logic: 4 points as shown below

void rearrangeLL(struct Node **head)

{

  struct Node *tortoise=*head, *hare=tortoise->next; //Floyd Cycle Finding Algo

  //1.Find middle using fast/slow pointer

  while(tortoise && hare && hare->next)

  {  tortoise=tortoise->next;  hare=hare->next->next; } //tortoise is middle pointer.

  //2. Split into two Linked list

  struct Node *half1=*head, *half2=tortoise->next;  tortoise->next=NULL;

  //3. Reverse second half

  reverseLL(&half2);

  //4. Merge Alternate nodes.

  struct Node *tmp=*head; //keep head pointer untouched.

  while(half1 || half2)

  {

    //Add one node from half1, and one from half2, move half1, half2 to next node each time.

    if(half1){ tmp->next=half1; tmp=tmp->next; half1=half1->next;}

    if(half2) { tmp->next=half2; tmp=tmp->next; half2=half2->next; }

  }

  *head=(*head)->next; //remember, we kept head pointer untouched

}

For circular list, finding middle element:

odd-elem: hare->next, even elem: hare->next->next will reach head, thus,

while(hare->next!=head && hare->next->next !=head)

{ hare=hare->next->next; tortoise->next; }

Detect cycle in Linked List [Rephrase: check if LL is NULL terminated]

Way 1: Use hash table. Traverse list, each time check if node address is in hash table.

Way 2: Smart and Efficient: Tortoise and Hare algo.

  struct Node *tortoise=head, *hare=tortoise->next;

  //1.Find middle using fast/slow pointer

  while(tortoise && hare && hare->next)

  {

    tortoise=tortoise->next;  hare=hare->next->next;

    if(tortoise==hare) hascycle=1

  }

Why can't sorting be used? Since we dont know length of LL.

Find starting node if there is cycle

if(hascycle==1)

{ tortoise=head;

   while(tortoise!=hare) { tortoise=tortoise->next; hare=hare->next; }

   return tortoise; //This is start of cycle

}

Find length of Cycle

Keep tortoise and move hare till it reaches tortoise again.

if(hascycle==1)

{ hare=hare->next;

   while(tortoise!=hare) { hare=hare->next; count++; }

   return count;

}

Check palindrome in List

1. Find middle pointer

2. Reverse 2nd half, compare with first half

3. Reverse 2nd half again to restore

References

http://www.geeksforgeeks.org/category/linked-list/ And browse from there.