Delete Xth Node From End of Linked List Editorial

Practice Problem Link: Delete 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, delete the xth node from the end.

Approach

Find the totalLength of the list and then simply delete 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* removeXthNodeFromEnd(ListNode* head, int x) {
	int totalLength = 0;
	ListNode *currentNode = head;
	while (currentNode != NULL) {
		currentNode = currentNode->next;
		totalLength++;
	}
	x = totalLength - x;
	currentNode = head;
	int i = 1;
	while(i < x) {
		i++;
	    currentNode = currentNode->next;
	}
	if (x == 0) {
		head = head->next;
		return head;
	}
	currentNode->next = currentNode->next->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 removeXthNodeFromEnd(ListNode head, int x) {
		int totalLength = 0;
		ListNode currentNode = head;
		while (currentNode != null) {
			currentNode = currentNode.next;
			totalLength++;
		}
		x = totalLength - x;
		currentNode = head;
		int i = 1;
		while(i < x) {
			i++;
			currentNode = currentNode.next;
		}
		if (x == 0) {
			head = head.next;
			return head;
		}
		currentNode.next = currentNode.next.next;
		return head;
	}
}

Another Approach

Take two pointers, say slow and fast. The slow pointer will be pointing to the start of the list and make the fast pointer point to the xth node from the start. Move both the pointers one node at a time until the fast pointer reaches the last node. At this moment the slow pointer must be pointing to the xth node from the last of the list and needs to be deleted.

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* removeXthNodeFromEnd(ListNode* head, int x) {
	ListNode* slow = head;
	ListNode* fast = head;
	for (int i = 1; i < x; i++) {
		fast = fast->next;
	}
	if (fast->next == NULL) {
		return head->next;
	}
	while (fast->next != NULL && fast->next->next != NULL) {
		fast = fast->next;
		slow = slow->next;
	}
	slow->next = slow->next->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 removeXthNodeFromEnd(ListNode head, int x) {
		ListNode slow = head;
		ListNode fast = head;
		for (int i = 1; i < x; i++) {
			fast = fast.next;
		}
		if (fast.next == null) {
			return head.next;
		}
		while (fast.next != null && fast.next.next != null) {
			fast = fast.next;
			slow = slow.next;
		}
		slow.next = slow.next.next;
		return head;
	}
}