Find 'n' th last element in a singly Linked list
  • node
  • linkedlist
  • stackqueuelinkedlist
  • singlylinkedlist
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2319)

Write an algortithm to find the \( n^{th} \) node from the last node of a singly Linked list.


Posted Answers


  • Take two pointers \( pointer1 \) and \( pointer2 \) pointing at the head of the Linked List.
  • Increment \( pointer2 \) by (\( n-1 \)) locations such that the distance between \( pointer1 \) and \( pointer2 \) becomes \( n \), \( i.e \), \( pointer2 \) now points \( n^{th} \) node.
  • Increment \( pointer1 \) and \( pointer2 \) by \( 1 \) until \( pointer2 \) reaches the last node of the list.
  • \( pointer1 \) now points to the \( n^{th} \) node from the last node of the list.

Time complexity = \( O(n) \).

LinkedListNode findNthNodeFromEnd(LinkedListNode head, int n){

/* Empty linked list */
if (head == null || n < 1)
return null;

/* Initialize two pointers at the beginning of the list */
LinkedListNode pointer1 = head;
LinkedListNode pointer2 = head;

/* Increment pointer2 by (n-1) locations */
for (int j = 0; j < n - 1; ++j){
/* When the length of the list is less than n */
if (pointer2 == null)
return null;
/* Increment 1 location */
pointer2 = pointer2.next;
}

/* Increment both the pointers until pointer2 reaches the last node */
while (pointer2.next != null){
pointer1 = pointer1.next;
pointer2 = pointer2.next;
}

/* pointer1 is now the nth node from the end - return it */
return pointer1;
}

You need to Sign In to post your solution.