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. Screen Shot 2020-01-23 at 9.51.00.png The following is an example of inversion for every 4 elements with k = 4. Screen Shot 2020-01-23 at 9.51.40.png

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: Screen Shot 2020-01-23 at 10.01.14.png

It feels like creating a partial inversion list for each k element and connecting it to the full inversion list. Screen Shot 2020-01-23 at 10.02.12.png Screen Shot 2020-01-23 at 10.06.26.png

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

Recommended Posts

Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm