Find kth node from the end

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 3. Find the kth node from the end of a linked list

We can treat the last node in the linked list as either the 0th node from the end or we can treat the last node as the 1st node from the end. So k can begin from 0 or 1. In the function below, we are treating the last node as the 1st node from the end. To find the kth node from the end, we first find the length of the linked list. Then we again traverse through the linked list to find the (length – k +1)th node from the beginning which corresponds to the kth node from the end. If the length of the linked list is n, then in the worst case we will access 2n nodes. The time complexity is O(n)

C/C++


/* 
head: first node of the linked list
k: node position from the end. k starts from 1 onwards
Return value: kth node from end if it exists, NULL otherwise
*/
struct node* find_kth_node_from_end(struct node *head, int k)
{
	struct node *n1;
	int i, length;

	length = 0;
	n1 = head;
	while (n1 != NULL) {
		length++;
		n1 = n1->next;
	}

	n1 = head;
	for (i = 1; i <= length; ++i) {
		if (i == length - k + 1) {
			return n1; 	/*n1 is the kth node from end. So return it*/
		}
		n1 = n1->next;
	}

	/*k value passed doesn't match with the linked list. So return NULL */
	return NULL;
}

Java


/* 
head: the first node of the linked list
k: node position from the end. k starts from 1 onwards
Return value: kth node from end if it exists, null otherwise
*/
public static LinkedListNode findKthNodeFromEnd(LinkedListNode head, int k) {
	int length = 0;

	LinkedListNode n1 = head;
	while (n1 != null) {
		length++;
		n1 = n1.next;
	}

	n1 = head;
	for (int i = 1; i <= length; ++i) {
		if (i == length - k + 1) {
			return n1; 	/*n1 is the kth node from end. So return it*/
		}
		n1 = n1.next;
	}

	/*k value passed doesn't match with the linked list. So return null */
	return null;

}

Python


#head: the first node of the linked list
#k: node position from the end. k starts from 1 onwards
#Return value: kth node from end if it exists, None otherwise
@staticmethod
def find_kth_node_from_end(head, k):
	length = 0
	n1 = head
	while (n1): 
		length += 1
		n1 = n1.next

	n1 = head
	for i in range(1, length + 1): 
		if (i == length - k + 1): 
			return n1 	#n1 is the kth node from end. So return it
	
		n1 = n1.next

	#k value passed doesn't match with the linked list. So return None
	return None

Reverse every K nodes

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 2. Reverse every k nodes in a linked list. So if the input is A->B->C->D->E->F->G->H and k is 3, then the output should be C->B->A->F->E->D->H->G

Both recursive and non-recursive solutions exist to reverse every k nodes with O(n) time complexity. Although the recursive solution takes more space, we will use it here since it is simpler. If there are n nodes in the linked list, we reverse the first k nodes and then recursively process the remaining n – k nodes. Let the linked list be A->B->C->D->E->F->G->H and k = 3. The diagram below illustrates the technique

C/C++


/* 
head: the first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
struct node * k_reverse_list(struct node *head, int k)
{
	struct node *cur_node,  *prev_node, *temp_node;
	int i = 0;

	if (!head || k == 0)
		return head;

	cur_node = head;
	prev_node = NULL;

	while (cur_node && i < k) {
		/*Store the next node in a temporary variable*/
		temp_node = cur_node->next;

		/*Reverse the link */
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = temp_node;

		++i;
	}

	/*
	We have reversed k nodes. cur_node points to the (k+1)th node
	and head points to the kth node.
	Now recursively process the remaining nodes from cur_node onwards 
	and assign the result to head->next.
	*/
	if (cur_node)
		head->next = k_reverse_list(cur_node, k);

	/*prev_node will point to first node in linked list after reversal*/
	return prev_node;
}

Java


/* 
head: first node of the linked list
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
public static LinkedListNode kReverseList(LinkedListNode head, int k) {
	int i = 0;

	if (head == null || k == 0)
		return head;

	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null && i < k) {
		/*Store the next node in a temporary variable*/
		LinkedListNode tempNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = tempNode;

		++i;
	}

	/*
	We have reversed k nodes. So curNode refers to the (k+1)th node.
	and head now refers to the kth node.
	Now recursively process the remaining nodes from curNode onwards 
	and assign the result to head.next.
	*/
	if (curNode != null)
		head.next = kReverseList(curNode, k);

	/*prevNode will refer to first node in linked list after reversal*/
	return prevNode;
}

Python


#head: first node of the linked list
#k: how many nodes should be reversed
#Return value: first node of the new linked list after reversing every k nodes
@staticmethod
def  k_reverse(head, k):
	if (not head or k == 0):
		return head

	cur_node = head
	prev_node = None
	i = 0
	while (cur_node and i < k): 
		#Store the next node in a temporary variable
		temp_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = temp_node

		i += 1

	#We have reversed k nodes. So cur_node refers to the (k+1)th node
	#and head refers to the kth node.
	#Now recursively reverse the remaining nodes from cur_node onwards 
	#and assign the result to head.next.
	if (cur_node):
		head.next = LinkedListNode.k_reverse(cur_node, k)

	#prev_node will refer to first node in the linked list after reversal
	return prev_node

Reverse a Linked List

admin / / Data Structures, Linked Lists

© Parineeth M R

Question 1. Reverse a linked list

A linked list can be reversed without using recursion by maintaining 3 nodes: prev_node, cur_node and next_node. As we traverse the linked list, we update the 3 nodes and the links in the linked list are reversed. The time complexity is O(n).

C/C++

/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
struct node* reverse_linked_list(struct node *head) {
	struct node *cur_node, *prev_node, *next_node;

	cur_node = head;
	prev_node = NULL;

	while (cur_node) {
		/*Store the next node in a temporary variable*/
		next_node = cur_node->next;

		/*Reverse the link so that current node points to the previous node*/
		cur_node->next = prev_node;

		/*Update the previous node to the current node */
		prev_node = cur_node;

		/*Proceed to the next node in the original linked list*/
		cur_node = next_node;
	}

	/*
	Once the linked list has been reversed, prev_node will be
	pointing to the new head. So return it
	*/
	return prev_node;
}

Java


/*Reverses the linked list without using recursion
head: first node in the original linked list 
Return value: the first node of the reversed linked list
*/
public static LinkedListNode reverseLinkedList(LinkedListNode head) {
	LinkedListNode curNode = head;
	LinkedListNode prevNode = null;

	while (curNode != null) {
		/*Store the next node in a temporary variable*/
		LinkedListNode nextNode = curNode.next;

		/*Reverse the link */
		curNode.next = prevNode;

		/*Update the previous node to the current node */
		prevNode = curNode;

		/*Proceed to the next node in the original linked list*/
		curNode = nextNode;
	}

	/*
	Once the linked list has been reversed, prevNode will have
	the new head. So return it
	*/
	return prevNode;
}

Python


#Reverses the linked list without using recursion
#head: first node in the original linked list 
#Return value: the first node of the reversed linked list
@staticmethod
def reverse(head):
	cur_node = head
	prev_node = None

	while (cur_node):
		#Store the next node in a temporary variable
		next_node = cur_node.next

		#Reverse the link 
		cur_node.next = prev_node

		#Update the previous node to the current node
		prev_node = cur_node

		#Proceed to the next node in the original linked list
		cur_node = next_node


	#Once the linked list has been reversed, prev_node will be
	#referring to the new head. So return it
	return prev_node