Reverse k Elements A single linked list and the integer "k" are passed as arguments. An algorithmic exercise that inverts k elements of a list. If k <= 1, the list is unchanged. If k> = n (n is the length of the linked list), reverse the entire linked list.
The following is an example of inversion for every 3 elements with k = 3. The following is an example of inversion for every 4 elements with k = 4.
Solution It's a relatively simple matter, but the code itself is a bit complicated because it needs to be tracked with a few pointers. The point in this algorithm is to "use two inverted lists". The first is a totally inverted list that is finally returned as a return value. The second is a partial (k element) inversion list that connects to the entire inversion list.
For example, suppose you have k = 5 and you have the following list:
It feels like creating a partial inversion list for each k element and connecting it to the full inversion list.
ReverseK.java
class ReverseK{
LinkedListNode reverse_k_nodes(LinkedListNode head, int k) {
if (k <= 1 || head == null) {
return head;
}
LinkedListNode reversed = null;
LinkedListNode prev_tail = null;
while (head != null & k > 0) {
LinkedListNode current_head = null;
LinkedListNode current_tail = head;
int n = k;
while (head != null && n > 0) {
LinkedListNode temp = head.next;
head.next = current_head;
current_head = head;
head = temp;
n--;
}
if (reversed == null) {
reversed = current_head;
}
if (prev_tail != null) {
prev_tail.next = current_head;
}
prev_tail = current_tail;
}
return reversed;
}
}
Recommended Posts