Algorithm exercises 13

Nth from the Last Node (Easy)

Description

Since the head node of the Singly Linked List and the integer n are passed, Let's implement an algorithm that returns the ** nth node from the end (returns null if n is out of range).

Solution The idea is to use two pointers n nodes apart. First set the first pointer to point to the head and the second to point to the nth node (default). If the second node reaches the final point of the list, null, during initialization, it returns null (out-of-bounds). Then move both pointers forward until the second pointer reaches the final point in the loop. After the loop ends, the first pointer will point to the nth node from the end, so we will return that pointer. Runtime Complexity O(n) The execution time is O (n) because the linear scan is performed on the Singley Linked List. Space Complexity O(1) Since it uses two pointers, the memory efficiency is a constant of O (1).

Example

Let's look at an example in the list below that searches for the third and last node (n = 3). As a default setting, move one pointer by n nodes. Move both pointers forward until the pointer you are moving forward reaches null at the final point. You have now found the penultimate node.

Implementation

lastNthFromList.java

class lastNthFromList{
  public LinkedListNode FindNthFromLast(LinkedListNode head,int n) {
    
    if (head == null || n < 1) return null; // edge case

    LinkedListNode targetNode = head;
    LinkedListNode searchNode = head;

    while (searchNode != null && n != 0) {
      searchNode = searchNode.next;
      n--;
    }

    if (n != 0) return null; // check out-of-bounds
    
    while(searchNode != null) {
      targetNode = targetNode.next;
      searchNode = searchNode.next;
    }

    return targetNode;
  }
}