## Find kth node from the end

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++

```
/*
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;
while (n1 != NULL) {
length++;
n1 = n1->next;
}

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

```
/*
k: node position from the end. k starts from 1 onwards
Return value: kth node from end if it exists, null otherwise
*/
int length = 0;

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

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

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

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

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++

```
/*
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)

prev_node = NULL;

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

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)

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

```

## Java

```
/*
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
int i = 0;

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

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

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)

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

```

## Python

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

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

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):

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

```

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
Return value: the first node of the reversed linked list
*/
struct node *cur_node, *prev_node, *next_node;

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
Return value: the first node of the reversed linked list
*/

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

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
#Return value: the first node of the reversed linked list
@staticmethod
prev_node = None

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

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

```