Add Element at Kth Position in Linked List Editorial

Practice Problem Link: Add 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, an integer k and an element, add that 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 insert the new element at k th index by doing the following:

• Change the next pointer value of new element to the kth element in the original linked list.
• Change the next pointer value of k-1 th element to the new 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* addAtkthElement (ListNode* head, int k, ListNode* newElement) {
    int index = 0;
	ListNode* currentNode = head;
	if(k == 1) {
		newElement->next = head;
		head = newElement;
		return head;
	}
	while(currentNode != NULL) {
		index++;
		if(index == k - 1) {
			break;
		}
		currentNode = currentNode->next;
	}
	newElement->next = currentNode->next;
	currentNode->next = newElement;
	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 addAtkthElement (ListNode head, int k, ListNode newElement) {
	    int index = 0;
		ListNode currentNode = head;
		if(k == 1) {
			newElement.next = head;
			head = newElement;
			return head;
		}
		while(currentNode != null) {
			index++;
			if(index == k - 1) {
				break;
			}
			currentNode = currentNode.next;
		}
		newElement.next = currentNode.next;
		currentNode.next = newElement;
		return head;
	}
}