Interview Questions

  • View all algorithm tutorials
  • blank
  • Find the middle element of a linked list
    A linked list is a data structure which consists of a group of nodes where each node may point to some other node to form a sequence. Our nodes will have two fields:
    (1) a "data" field which will store our data (string, number, etc.) (2) a "next" field which will be a reference to some other node
    Linked lists are useful and simple data structures and are sometimes preferred over using arrays because inserting or deleting elements can be done without reallocation or reorganization of the entire structure. If, for example, you wanted to add an element to the beginning of the array, every single other element would need to be moved and the array would need to make space for one extra element. Inserting an element at the beginning of a linked list simply requires you to create a new node and set its "next" field to point to some node, making this new node the first node in the sequence now.

    Node setup

    function Node(data, next) {
      this.data = data;
      this.next = next;
    }            
    
    class Node:
      def __init__(self, data, next):
        self.data = data
        self.next = next                     
    
    This is how we can then create a linked list with connecting nodes:
    var n1 = new Node("Hello", null);   
    var n2 = new Node("21", n1); 
    var n3 = new Node("Green", n2); 
    
    // assign a node to the head which functions
    // as the entry into our linked list
    var head = n3;       
    
    n1 = Node("Hello", None)
    n2 = Node("21", n1) 
    n3 = Node("Green", n2)  
    
    # assign a node to the head which functions
    # as the entry into our linked list   
    head = n3               
    
    Our challenge is to now find the middle node in a linked list. We don't initially know the length of a linked list, all we have is a single node which acts as the head of the linked list and which we can access all other nodes by traversing through each nodes "next" property. We can continuously loop through each node until we get to a node that has a "next" property of null, which means we have reached the last node.

    Naive solution

    A simple way to determine the middle node would be to fully pass through all nodes in the linked list and count how many elements there are in total. Then traverse the linked list again this time stopping at the total/2 node. For example, the first time you traverse the linked list your program determines there are 10 nodes, then the second pass through the linked list you stop at the 5th node, which is the middle node. This is a possible solution, but there is a faster way.

    Faster solution using 2 pointers

    What we'll do is setup two pointers, one that will traverse the linked list one node at a time, and the other pointer will traverse two nodes at a time. This way when the faster pointer reaches the end of the linked list, the slower pointer will be halfway there because it was only moving one node at time while the faster one was moving two nodes at a time. This allows you to find the middle node of a linked list with only one pass, instead of passing through the whole linked list once, and then again to find the middle element.
    function Node(data, next) {
      this.data = data;
      this.next = next;
    }    
    
    // setup some nodes and connect them to each other
    // the linked list looks like:
    // (head) n5 -> n4 -> n3 -> n2 -> n1 -> null
    var n1 = new Node("Hello", null);   
    var n2 = new Node("21", n1); 
    var n3 = new Node("Green", n2); 
    var n4 = new Node("Blue", n3); 
    var n5 = new Node("Daniel", n4); 
    
    // assign a node to the head which functions
    // as the entry into our linked list
    var head = n5; 
    
    // setup pointers to both start
    // at the head of the linked list
    var fastPointer = head;
    var slowPointer = head;
    
    // loop through the linked list
    // when fastPointer reaches the end of the list
    // then slowPointer will be at the middle node
    while (fastPointer.next !== null && fastPointer.next.next !== null) {
      fastPointer = fastPointer.next.next;   
      slowPointer = slowPointer.next;
    }
    
    // slowPointer is now at the middle node in the linked list
    slowPointer.data  
    
    class Node:
      def __init__(self, data, next):
        self.data = data
        self.next = next 
    
    # setup some nodes and connect them to each other
    # the linked list looks like:
    # (head) n5 -> n4 -> n3 -> n2 -> n1 -> None
    n1 = Node("Hello", None)  
    n2 = Node("21", n1)
    n3 = Node("Green", n2) 
    n4 = Node("Blue", n3)
    n5 = Node("Daniel", n4)  
    
    # assign a node to the head which functions
    # as the entry into our linked list
    head = n5
    
    # setup pointers to both start
    # at the head of the linked list
    fastPointer = head
    slowPointer = head
    
    # loop through the linked list
    # when fastPointer reaches the end of the list
    # then slowPointer will be at the middle node
    while fastPointer.next != None and fastPointer.next.next != None:
      fastPointer = fastPointer.next.next
      slowPointer = slowPointer.next
      
    # slowPointer is now at the middle node in the linked list
    print slowPointer.data            
    
    Run Code
    Run Code

    Running time

    The running time of finding the middle element this way with two pointers is O(n) because once we pass through the entire linked list of n elements, the slower pointer is at the middle node already.

    Sources

    http://www.careercup.com/question?id=1434688
    mrdaniel published this on 11/9/15 | linked list, search, Google
    Comments
  • +
  • 7
  • -
  • Nice Pass. I was just wondering why can't we directly assign n5 to fastPointer and slowPointer rather than assigning n5 to head first?
  • +
  • 2
  • -
  • If that was directly done, it won't be as clear as now. For demostration purposes, head needs to be clearly defined. In fact, it took O(1) only, not a big deal.
  • +
  • 0
  • -
  • Ah one while loop instead of 2. Yeah my bad...
  • +
  • 0
  • -
  • How is this any better than traversing the entire thing? The two pointer jump is traversing the entire thing, to figure out how to jump twice it jumps once to get the next pointer then jumps again. Just because the code seems shorter does not mean this solution is faster, unless by faster you mean to type rather than to run. You still passed the link list twice, once fully with the "fast pointer" who still had to go through the nodes one by one on the low level to figure out how to path through, and once half a time with the slow pointer. I must be missing something here, someone please explain to me why it is faster.
  • +
  • 0
  • -
  • class Node:
            def __init__(self, data, next):
                    self.data=data
                    self.next=next
    
    n1 = Node("Hello ,", None)
    n2 = Node("World, ", n1) 
    n3 = Node("Gray", n2)    
    head = n3
    fastPointer=head
    slowPointer=head
    while fastPointer.next !=None and  fastPointer ==None:
            fastPointer=fastPointer.next
            slowPointer=slowPointer.next    
    print(slowPointer.data)
  • +
  • 0
  • -
  • @mrj936, the idea is that you are only looping over the list once. The pointer accesses inside the loop are fast operations and do not increase the time complexity of the algorithm (see https://en.wikipedia.org/wiki/Time_complexity) The time complexity for this algorithm is O(n), where n is the number of entries in the list. If you used an algorithm that traverses the list twice, it would be 2 * O(n), which has the same time complexity from a mathematical standpoint, but in practice would be up to twice as slow.
    Log in to submit a comment.