Reverse k Elements

단일 링크 목록과 정수 "k"가 인수로 전달됩니다. 리스트의 k요소씩 반전시키는 알고리즘 체조.
k<=1이면 목록은 변경되지 않습니다. k >= n(n은 링크 목록 길이)이면 전체 링크 목록을 뒤집습니다.

예

다음은 k = 3이고 3요소마다 반전한 예입니다.

다음은 k = 4이고 4개 요소마다 반전된 예입니다.

Solution

비교적 간단한 문제이지만 코드 자체는 몇 가지 포인터로 추적해야하기 때문에 약간 복잡합니다.
이 알고리즘의 핵심은 두 개의 반전 목록 사용입니다.
첫 번째는 결국 반환 값으로 반환하는 전체 반전 목록.
둘째가 전체 반전 리스트에 연결해 가는 부분(k요소) 반전 리스트.

reversed : 전체 반전 리스트의 선두를 가리키는 포인터. 반환값이 됩니다.

current_head: 사이즈 「k」의 부분 반전 리스트의 선두.

current_tail: 사이즈 'k'의 부분 반전 리스트의 말미.

prev_tail: 이미 처리된 전체 반전 목록의 끝.

예를 들어, k = 5이고 다음 목록이 있다고 가정합니다.


k요소씩 부분 반전 리스트를 만들어 전체 반전 리스트에 연결해 나가는 느낌이 듭니다.

구현

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