Kth Element in Linked List Editorial

Practice Problem Link: Kth Element in Linked List

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

Problem Statement

Given a linked list, find the element at the kth position.

Approach

The idea is to simply traverse the linked list till the count of elements is less than k and then return the kth element.

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