Remove Element at Kth Position in Linked List Editorial

Practice Problem Link: Remove Element at Kth Position in Linked List

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

Problem Statement

Given a Linked List and an integer k, remove the element at the kth position of the linked list.

Approach

The idea is to traverse the given linked list up to k-1 th index and change the next pointer value of the k-1 th index to k+1 th index.

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* removekthElement (ListNode* head, int k) {
    int index = 0;
	ListNode* currentNode = head;
	if (k == 1) {
		return head->next;
	}
	while(currentNode != NULL) {
		index++;
		if(index == k - 1) {
			break;
		}
		currentNode = currentNode->next;
	}
	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 removekthElement (ListNode head, int k) {
	    int index = 0;
		ListNode currentNode = head;
		if (k == 1) {
			return head.next;
		}
		while(currentNode != null) {
			index++;
			if(index == k - 1) {
				break;
			}
			currentNode = currentNode.next;
		}
		currentNode.next = currentNode.next.next;
		return head;
	}
}