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). Screen Shot 2020-01-09 at 19.07.12.png As a default setting, move one pointer by n nodes. Screen Shot 2020-01-09 at 19.08.10.png Move both pointers forward until the pointer you are moving forward reaches null at the final point. Screen Shot 2020-01-09 at 19.12.02.png Screen Shot 2020-01-09 at 19.12.22.png Screen Shot 2020-01-09 at 19.12.49.png 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;
  }
}

Recommended Posts

Algorithm exercises 13
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm exercise 6
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm Gymnastics 15
Python algorithm
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Python memorandum (algorithm)
Pandas exercises (editing)
Dictionary learning algorithm
String search algorithm