Algorithm Gymnastics 18

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.

Example

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.

1. reversed: A pointer to the beginning of the totally reversed list. It will be the return value.
2. current_head: The head of the partially inverted list of size "k".
3. current_tail: The end of the partially inverted list of size'k'.
4. prev_tail: The end of the fully inverted list that has already been processed.

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.

Implementation

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;
  }
}