Problem

Given a linked list and integer n, write an algorithm to find the nth node from the end in the linked list.

Examples

Example 1:

1
2
3
4
5

Input: head=[1, 2, 8, 3, 7, 0, 4], n = 3
Output : 7
Explanation: 3rd Element from the end is : 7
1->2->8->3->7->0->4
            3  2  1 <- indices from end

Solution

Method 1 – Naive - Finding Number of Nodes

We can first the size len of linked list and then loop from start to len - n nodes. Here is the code to Find the length of the linked list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public ListNode getNthNodeFromLast(ListNode head, int n) {

	ListNode curr = head;
	int len = size(head); // takes O(n)

	// assign current to head of the list
	curr = head;

	// nth node from end means (len-n)th node from start (assuming n is valid)
	int counter = len - n;

	while (counter != 0) {
		// n is greater than size (len) of the linked list
		// current pointer reaches null
		if (curr == null) {
			return null;
		}

		curr = curr.next;
		counter--;
	}

	return curr;
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of linked list
  • 🧺 Space complexity: O(1)

Method 2 - Recursion

  • Recursively traverse the linked list.
  • Upon reaching the end, the base case will return 0.
  • As the stack unwinds, increment the count and return it.
  • When the count equals n, print the value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {

	public ListNode getNthFromEnd(ListNode head, int n) {
		ListNode[] ans = ListNode[1];
		helper(head, n, ans);
		return ans[0];
	}

	private int helper(ListNode head, int n, ListNode[] ans) {
		if (head == null) {
			return 0;
		}

		int index = helper(head.next, n, ans) + 1;

		if (index == n) {
			ans[0] = head;
		}

		return index;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of linked list
  • 🧺 Space complexity: O(n), assuming recursion stack

Method 3 – Using Two Pointer Technique

Algo

  1. Initialize slow and fast pointers at the head of the list.
  2. Move the fast pointer forward by n steps. If the fast pointer reaches the end before completing n steps, return null (indicating n is greater than the list’s length).
  3. Move both slow and fast pointers one step at a time, maintaining a distance of n nodes between them.
  4. Continue this until the fast pointer reaches the end of the list.
  5. Return the slow pointer, as it will be n nodes from the end, which is the target node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public ListNode getNthNodeFromLast(ListNode head, int n) {

	ListNode slow = head, fast = head;
	int i = 0;

	// Traverse over list and move fast pointer n nodes ahead 
	while (i < n && fast != null) {
		fast = fast.next;
		i++;
	}

	if (fast == null) {
		return null; // List is shorter than n nodes
	}

	// Now, move both pointers together until fast reaches the end
	while (fast != null) {
		slow = slow.next;
		fast = fast.next;
	}

	return slow;
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of linked list
  • 🧺 Space complexity: O(1)

Dry Run