Find xth Node from End of Linked List Editorial

Practice Problem Link: Find xth Node From End of Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list, find the xth node from the end.

Approach

Find the totalLength of the list and then simply return the (totalLength - x + 1)th node from the start of the linked list.

Analysis

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

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* xthNodeFromEnd(ListNode* head, int x) {
	int totalLength = 0;
	ListNode *currentNode = head;
	while (currentNode != NULL) {
		currentNode = currentNode->next;
		totalLength++;
	}
	x = totalLength - x;
	currentNode = head;
	int i = 0;
	while(i < x) {
		i++;
	    currentNode = currentNode->next;
	}
	return currentNode;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode xthNodeFromEnd(ListNode head, int x) {
		int totalLength = 0;
		ListNode currentNode = head;
		while (currentNode != null) {
			currentNode = currentNode.next;
			totalLength++;
		}
		x = totalLength - x;
		currentNode = head;
		int i = 0;
		while(i < x) {
			i++;
			currentNode = currentNode.next;
		}
		return currentNode;
	}
}

Another Approach

Take a pointer say front and make it point to the xth node from the start of the list. Now move the front pointer and the head pointer one node at a time until the front pointer reaches the last node. At this moment the head pointer must be pointing to the xth node from the end of the list.

Analysis

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

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* xthNodeFromEnd(ListNode* head, int x) {
	ListNode* front = head;
	for (int i = 1; i < x; i++) {
		front = front->next;
	}
	if (front->next == NULL) {
		return head;
	}
	while (front->next != NULL) {
		front = front->next;
		head = head->next;
	}
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode xthNodeFromEnd(ListNode head, int x) {
		ListNode front = head;
		for (int i = 1; i < x; i++) {
			front = front.next;
		}
		if (front.next == null) {
			return head;
		}
		while (front.next != null) {
			front = front.next;
			head = head.next;
		}
		return head;
	}
}