Finding Nth node from end of a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Finding first node in a Loop in Singly Linked List.

Figure 1: Singly Linked List

Solution 01 - Brute Force Approach:

1. Start at First Node of the List (call it curNodePtr).
2. Assign curNodePtr to tmpPtr and count number of nodes after the curNodePtr.
3. If number of nodes after curNodePtr are equal to N nodes or tmpPtr reaches END then break. If tmPtr reaches END but count not equal to N then return since we can't find the Nth node from the end of the Singly Linked List.
4. Move the curNodePtr one step forward in the Linked List i.e curNodePtr now points to its next node in the list and start again from STEP-2.

Pseudocode:

curNodePtr := FirstNode

if curNodePtr == NULL
  return 'Less Nodes in the List'

forever:

  tmpPtr := curNodePtr
  count := 0

  forever:

    if tmpPtr == NULL || count == N
      break

    tmpPtr := tmpPtr.NEXT
    count++

  if tmpPtr == NULL
    if count == n
      return curNodePtr
    else
      return 'Less Nodes in the List'

  curNodePtr := curNodePtr.NEXT 

Complexity:

• Time Complexity: O(n^2) - For traversing each node after curNode.
• Space Complexity: O(1)

Example:

Let us try above brute-force approach on example in Figure-1

Find 2nd Node: It returns Node 4.

curNode     tmpNode   Count
01                    01            0
01                    02            1
01                    03            2
02                    02            0
02                    03            1
02                    04            2
03                    03            0
03                    04            1
03                    05            2
04                    04            0
04                    05            1
04                    NULL       2 

Find 6th Node: It returns 'Less Nodes in the List'

curNode     tmpNode   Count
01                    01            0
01                    02            1
01                    03            2
01                    04            3
01                    05            4  
01                    NULL       5 

Solution 02:

Let us improve the time complexity when compared to Solution-01.

1. Find the length of the Singly Linked List (Let us say P).
2. If Length of the Singly linked List (P) is lesser than N return, since we can't find the Nth node from the end of the Singly Linked List.
3. If Length of the Singly Linked List (P) greater than N then compute (P-N+1) value, which points to Nth node from the end of Singly Linked List.
4. Traverse to (P-N+1)th Node in the Singly Linked List.

Pseudocode:

curNodePtr := FirstNode
P = 0

forever:

  if curNodePtr == NULL
    break

  P++
  curNodePtr := curNodePtr.NEXT

if P < N
  return 'Less Nodes in the List'

curNodePtr := FirstNode
count = 1

forever:

  if count == (P-N+1)
    return curNodePtr

  count++
  curNodePtr = curNodePtr.NEXT

Complexity:

• Time Complexity: O(n) - Time for finding the length of a Singly Linked List O(n) + Time for finding (P-N+1) node in the List O(n) = O(n)
• Space Complexity: O(1)

Solution 03:

Let us see one more simple and cleaner approach when compared to Solution 02 which doesn't need to traverse all nodes in the list twice to find the Nth node from the end of a Singly Linked List.

1. Let us take two pointers tmpPtr and nthNodePtr starting at the First Node of the Singly Linked List.
2. tmpPtr will start first by traversing N positions in the list. If it doesn't reach N positions from start of the singly linked list it means list is small. Return as we can't find the Nth node from the end of the list.
3. Once tmpPtr traverses N positions successfully nthNodePtr starts traversing along with tmpPtr one position forward until tmpPtr reaches the end of the List.
4. Once tmpPtr reaches end of the Singly Linked List nthNodePtr will be pointing to Nth node from the end of the Singly Linked List

Pseudocode:

tmpPtr := FirstNode
nthNodePtr := FirstNode
count := 1

forever:
  
  if count == N || tmpPtr == NULL
    break

  tmpPtr := tmpPtr.NEXT
  count++

if tmpPtr == NULL && count < N
  return 'Cannot find Nth element in the list'

tmpPtr := tmpPtr.NEXT

forever:

  if tmpPtr == NULL
    return nthNodePtr

  tmpPtr := tmpPtr.NEXT
  nthNodePtr := nthNodePtr.NEXT 

Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Example:

Let us try the above solution on example in Figure-1

Find 2nd Node from end of the List

tmpPtr  nthNodePtr  count
    1             1               1
    2             1               2
    3             1               -
    4             2               -  
    5             3               -
    NULL      4               -