Other interview questions

• How to Reverse a list
  
• Find the middle of a given linked list:
  Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

  Idea: Keep two pointer at the same time

• Given a singly linked list, determine if its a palindrome. This method takes O(n) time and O(1) extra space.
  1) Get the middle of the linked list. 
  2) Reverse the second half of the linked list. 
  3) Check if the first half and second half are identical. 
  4) Construct the original linked list by reversing the second half again and attaching it back to the first half.

  Idea: 1) find the middle 2)reverse

• Flatten A Binary Tree to Linked List (In-place) Go down through the left, when right is not null, push right to stack.
  

  
  
  

• Swap nodes in a linked list without swapping data.
  The idea it to first search x and y in given linked list. If any of them is not present, then return. While searching for x and y, keep track of current and previous pointers.
• Given only a pointer/reference to a node to be deleted in a singly linked list, how do you delete it?
  is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.
• Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. MergeSort(headRef)
  1) If head is NULL or there is only one element in the Linked List  
      then return.  
  2) Else divide the linked list into two halves.  
        FrontBackSplit(head, &a, &b); /* a and b are two halves */  
  3) Sort the two halves a and b.  
        MergeSort(a);  
        MergeSort(b);  
  4) Merge the sorted a and b (using SortedMerge() discussed here)  
     and update the head pointer using headRef.  
       *headRef = SortedMerge(a, b);

  Idea: 1) No random access 2) recursive

  /* sorts the linked list by changing next pointers (not data) */ 
  void MergeSort(struct node** headRef) 
  { 
    struct node* head = *headRef; 
    struct node* a, b; 
   
    /* Base case -- length 0 or 1 */ 
    if ((head == NULL) || (head->next == NULL)){ 
      return; 
    } 
   
    /* Split head into ’a’ and ’b’ sublists */ 
    FrontBackSplit(head, &a, &b); 
   
    /* Recursively sort the sublists */ 
    MergeSort(&a); 
    MergeSort(&b); 
   
    /* answer = merge the two sorted lists together */ 
    *headRef = SortedMerge(a, b); 
  }
  /* See http://geeksforgeeks.org/?p=3622 for details of this 
     function */ 
  struct node* SortedMerge(struct node* a, struct node* b) 
  { 
    struct node* result = NULL; 
   
    /* Base cases */ 
    if (a == NULL) 
       return(b); 
    else if (b==NULL) 
       return(a); 
   
    /* Pick either a or b, and recur */ 
    if (a->data <= b->data){ 
       result = a; 
       result->next = SortedMerge(a->next, b); 
    } 
    else{ 
       result = b; 
       result->next = SortedMerge(a, b->next); 
    } 
    return(result); 
  }
  /* UTILITY FUNCTIONS */ 
  /* Split the nodes of the given list into front and back halves, 
       and return the two lists using the reference parameters. 
       If the length is odd, the extra node should go in the front list. 
       Uses the fast/slow pointer strategy.  */ 
  void FrontBackSplit(struct node* source, 
            struct node** frontRef, struct node** backRef) 
  { 
    struct node* fast; 
    struct node* slow; 
    if (source==NULL || source->next==NULL) 
    { 
      /* length < 2 cases */ 
      *frontRef = source; 
      *backRef = NULL; 
    } 
    else 
    { 
      slow = source; 
      fast = source->next; 
   
      /* Advance ’fast’ two nodes, and advance ’slow’ one node */ 
      while (fast != NULL) 
      { 
        fast = fast->next; 
        if (fast != NULL) 
        { 
          slow = slow->next; 
          fast = fast->next; 
        } 
      } 
   
      /* ’slow’ is before the midpoint in the list, so split it in two 
        at that point. */ 
      *frontRef = source; 
      *backRef = slow->next; 
      slow->next = NULL; 
    } 
  }
• Merge Two sorted lists.
  /* Takes two lists sorted in increasing order, and splices 
     their nodes together to make one big sorted list which 
     is returned.  */ 
  struct node* SortedMerge(struct node* a, struct node* b){ 
      /* a dummy first node to hang the result on */ 
      struct node dummy; 
      /* tail points to the last result node  */ 
      struct node* tail = &dummy; 
   
      /* so tail->next is the place to add new nodes 
        to the result. */ 
      dummy.next = NULL; 
      while (1){ 
          if (a == NULL)        { 
              /* if either list runs out, use the 
                 other list */ 
              tail->next = b; 
              break; 
          } 
          else if (b == NULL){ 
              tail->next = a; 
              break; 
          } 
          if (a->data <= b->data) 
              MoveNode(&(tail->next), &a); 
          else 
              MoveNode(&(tail->next), &b); 
   
          tail = tail->next; 
      } 
      return(dummy.next); 
      //dummy code will be destoried. 
  }
  /* UTILITY FUNCTIONS */ 
  /* MoveNode() function takes the node from the front of the 
     source, and move it to the front of the dest. 
     It is an error to call this with the source list empty. 
     Before calling MoveNode(): 
     source == {1, 2, 3}  dest == {1, 2, 3} 
     Affter calling MoveNode(): 
     source == {2, 3}  dest == {1, 1, 2, 3} */ 
  void MoveNode(struct node** destRef, struct node** sourceRef) 
  { 
      /* the front source node  */ 
      struct node* newNode = *sourceRef; 
      assert(newNode != NULL); 
   
      /* Advance the source pointer */ 
      *sourceRef = newNode->next; 
   
      /* Link the old dest off the new node */ 
      newNode->next = *destRef; 
   
      /* Move dest to point to the new node */ 
      *destRef = newNode; 
  }
• fun1() prints the given Linked List in reverse manner.
  void fun1(struct node* head){ 
    if(head == NULL) 
      return; 
   
    fun1(head->next); 
    printf("%d␣␣", head->data); 
  }

  Idea: recursive

• Write a program function to detect loop in a linked list
  This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

  a circle has at last three nodes, so fast pointer each time step 2, So it will always go around inside the circle

• Conclusion:
  1. Just like tree, link-list problems can be resolved by recursive.
  2. Most of time, In single link list, you need to keep previous pointer.

  	array	list
  insert erase	O(n)	O(1)
  sort	quicksort	mergesort
  reverse	swap element	just manipulate pointer
  rotate	easy pointer manipulate	swap element
  merge
  other

  1. in STL, For assign, insert, erase and constructor, vector support two version, one is single element, other is range. When we deal wih range input, we prefer to use range version.
  2. std::list and std::vector has different big O for insert and erase.
  3. std::list has its own sort member function, but std::vector doesn’t have. you can use std::sort algorithme.
  4. std::list has its own reverse, std::vector doesn’t have, just use std::reverse algorithm
  5. list and vector don’t have their own rotate function.
  6. list has its own merge, vector use std::merge algorithm.