Alex Rivera | Logout

How to find nth element from the end of a singly linked list?

Asked 2010-04-08T08:03:56.907
66

The following function is trying to find the nth to last element of a singly linked list.

For example:

If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7.

Can anybody help me on how this code is working or is there a better and simpler approach?

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
    if (p2 == null) {
      return null; // not found since list size < n
    }
    p2 = p2.next;
  }

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}
algorithm linked-list data-structures
Edit
Report

3 Answers

68

The key to this algorithm is to set two pointers p1 and p2 apart by n-1 nodes initially so we want p2 to point to the (n-1)th node from the start of the list then we move p2 till it reaches the last node of the list. Once p2 reaches end of the list p1 will be pointing to the nth node from the end of the list.

I've put the explanation inline as comments. Hope it helps:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nt
answered 2010-04-09T05:07:41.313
2

Since this sounds like homework, I prefer to help you help yourself instead of giving an actual solution.

I suggest you run this code on some small sample dataset. Use your debugger to run lines step-by-step (you can set a breakpoint at the start of the function). This should give you an idea of how the code works.

You can also Console.WriteLine() to output variables of interest.

answered 2010-04-08T08:16:00.817
0

You can also solve the above problem using hash tables.The entries of the hash table are position of node and address of node. So if we want to find the nth node from the end(this means m-n+1 from the first where m is number of nodes).Now when we enter the hash table entries we get the number of nodes.Steps are:-

1.Traverse each node and make corresponding entries in hash table.

2.Look for the m-n+1 node in hash table we get the address.

Time complexity is O(n).

answered 2012-08-18T06:32:44.917

Your Answer