Necessary and Sufficient

Question: Write a C++ function that takes a singularly-linked list and reverses it. It must have linear, O(n), run time - that is you are only allowed to make 1 pass through the list. No changes to the list data can be made and no additional data structures can be used.

This is similar to the recursive reverse problem.

Solution: This is an exercise in pointer manipulation and understanding the difference between pass by value and pass by reference. All we need to do is to traverse the list keeping a reference/pointer to the last node visited and for the current node tweak the "next" pointer to point to the last node. Of course, before we overwrite the "next" pointer we need to take a copy of it first, otherwise we wouldn't be able to continue the list traversal. The hidden danger in this problem is making sure the head pointer is accurate at the end of the list traversal.

Here's my C++ code to do this:

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not necessary in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  void reverse(node** head){

  18:      node* current = *head;

  19:      node* last = NULL;

  20:      node* oldNext = current;

  21:   

  22:      while (current != NULL){

  23:          oldNext = current->next;

  24:          current->next = last;

  25:          last = current;

  26:          current = oldNext;

  27:      }

  28:      *head=last;

  29:  }

  30:   

  31:  int main(){

  32:      

  33:      node* head= NULL;    

  34:          

  35:      for(int i=7; i>=1;i--){

  36:          push(&head, i);

  37:      }

  38:      

  39:      node* current = head;

  40:      while(current != NULL)

  41:      {

  42:          printf("%d ",current->data);

  43:          current = current->next;

  44:      }

  45:   

  46:      reverse(&head);

  47:      printf("\n");

  48:   

  49:      current = head;

  50:      while(current != NULL)

  51:      {

  52:          printf("%d ",current->data);

  53:          current = current->next;

  54:      }

  55:  }

In the code above we use 3 node pointers (in lines 18-20) to keep track of the current node and the one before and after it. Along these same lines there is an alternative approach to the reverse problem that employs 3 iterators, called back, middle, front which effectively does the same thing as the algorithm above. For completeness, here is the 3-iterators approach:

   1:  // the three-pointer approach

   2:  void reverse2(node** head){

   3:      if (*head != NULL){

   4:          node* middle=*head;

   5:          node* front =middle->next;

   6:          node* back=NULL;

   7:          

   8:          while(true){

   9:              middle->next = back;    // reverse the middle node

  10:              

  11:              // move all pointers forward

  12:              if (front == NULL)

  13:                  break;

  14:   

  15:              back = middle;

  16:              middle = front; 

  17:              front = front->next;

  18:          }

  19:          *head = middle;

  20:      }

  21:  }

Question: Write a C++ function that makes a deep copy of a linked list.

Answer: This is a good interview question because it examines several concepts: pointer operations, pass by reference, and stack vs heap allocation. To answer the question you need to first understand the different between deep and shallow copies.

In a deep copy, sometimes refered to as memberwise copy, the copy operation respects object semantics. That means that if the object being copied has pointers/references to other objects those objects need to be duplicated, rather than just having duplicate pointers/references to the existing dependent objects. In other words, all ties to the existing "parts" are severed.

On the other hand shallow copy, or bitwise copy, does not respect object semantics. It copies all of the objects fields but it does not create new copies of any dependent object. Instead it creates copies of the pointers/references to these dependent objects. For reference types, this is usually not what you want!

So back to our linked list problem... Each node in a linked list is a struct. To make a deep copy of the list we want to duplicate the nodes and create an entirely new linked link that strings them together in the same logical sequence as the original linked list.

Here is some C++ code (lines 27-44) to do the deep copy and also to verify the results by way of a simple count function and walking the list. It is possible to write a recursive copy function but the stack space consumed will be proportional to the length of the input list.

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not reqd in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  int length(node* start){

  18:      int count=0;

  19:      node* current = start;

  20:      while(current != NULL){

  21:          count++;

  22:          current = current->next;

  23:      }

  24:      return count;

  25:  }

  26:   

  27:  node* copy(node* head){

  28:      node* current = head;

  29:      node* newHead = NULL;

  30:      node* newTail = NULL;

  31:   

  32:      while(current != NULL){

  33:          if(newHead == NULL){

  34:              push(&newHead, current->data);

  35:              newTail = newHead;

  36:          }

  37:          else {

  38:              push(&(newTail->next),current->data);

  39:              newTail = newTail->next;

  40:          }

  41:          current = current->next;

  42:      }

  43:      return newHead;

  44:  }

  45:   

  46:  int main(){

  47:      

  48:      node* head2= NULL;    

  49:          

  50:      for(int i=7; i>=1;i--){

  51:          push(&head2, i);

  52:      }

  53:      

  54:      node* head = copy(head2);

  55:   

  56:      int len=length(head);

  57:      printf("Length of list is %d\n",len);

  58:   

  59:      node* current = head;

  60:      while(current != NULL)

  61:      {

  62:          printf("%d ",current->data);

  63:          current = current->next;

  64:      }

  65:  }

Question: How do you find the middle item in a list, or linked list without using the Count() property. This question is more common in C/C++ circles where linked lists are more prevalent and their use of pointers make things a touch more hairy for inexperienced developers.

Answer: In C#, List<T> and LinkedList<T> both implement IEnumerable<T>. Because of this we can write a generic function that operates on an IEnumerable<T> to handle both cases. So how to solve the problem? If IEnumerable <T> supported both forward and backward iteration, like a doubly linked list does, we could walk the list from both ends and they'd have to meet in the middle. Unfortunately we can't do that, enumerators in C# are effectively "fire hose cursors" - that is forward-only. Instead we can start two concurrent enumerations, one that steps forward 1 step at a time and one that steps forward 2 steps at a time. When the faster enumerator reaches the end of the list, the slower enumerator will be at the middle element. Note that this assumes that there aren't cycles in the list. Here's some C# code to do this.

        public static T ListMiddle<T>(IEnumerable<T> input)
        {
            if (input == null)
                return default(T);

            var slow = input.GetEnumerator();
            var fast = input.GetEnumerator();

            while (slow.MoveNext())
            {
                if (fast.MoveNext())
                {
                    if (!fast.MoveNext())
                        return slow.Current;
                }
                else
                {
                    return slow.Current;
                }
            }
            return slow.Current;
        }

And if C++ is your language you just need 2 pointers to the head of the single-linked list and you start a tortoise and hare race. When the hare (fast-moving pointer), which advances in 2-node steps, get to the end the tortoise (slowly-advancing pointer) will be at the middle - or thereabouts if the number of nodes is even. This assumes there are no cycles in the list. If there are an infinite loop results so we'd want to plug in loop-detection logic before pushing this to a live system! Here's some C++ code to demo this:

#include <stdio.h>
#include <stdafx.h>
#include <malloc.h>

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

node* findMiddle(node* head)
{
    node* fast;
    node* slow;

    slow=fast=head;
    while(fast->next && fast->next->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

int main()
{
    node* head= new node;
    node* second= new node;
    node* third= new node;

    head->data =1;
    head->next = second;

    second->data =2;
    second->next = third;

    third->data =3;
    third->next = NULL;

    node* mid=findMiddle(head);
    printf("Middle node is %d\n",mid->data);
}