Rotate a Linked List

설명

단일 링크 리스트의 헤드 노드와 정수 n 를 지정하면(자), 링크 리스트를 n 회전시키는 알고리즘 체조.

다음 두 가지 예가 있습니다. 인수로서 건네받은 링크 리스트와 정수 n = 2 회전 후의 출력입니다.

n 의 값은, 링크 리스트의 길이보다 커질 가능성이 있는 것에 주의해 주세요.


n = -2일 때,

Solution

Runtime Complexity O(n)

n은 링크 목록의 길이입니다.

Memory Complexity O(1)

새로운 데이터 구조를 사용할 필요가 없습니다. 포인터 전용.

먼저 링크 목록의 길이를 찾습니다.

n이 음수이거나 n이 링크 목록 길이보다 큰 경우 링크 목록 끝에 필요한 회전 수에 맞게 조정합니다.
조정된 숫자는 항상 정수 N입니다(0<=N

링크 목록의 마지막 노드에서 n번째 'x' 노드를 찾습니다. 기본적으로 길이 "n-N"으로 노드 x에 도달합니다. 이 노드의 이전 노드의 다음 포인터는 목록의 끝에있는 노드가되므로 NULL을 가리 키도록 업데이트해야합니다.

x에서 링크 목록의 마지막 노드로 이동합니다. 마지막 노드의 다음 포인터를 헤드 노드로 업데이트합니다.

새 헤드 노드로 new_head를 만듭니다. new_head 는, n회의 회전을 실행한 후의 링크 리스트의 선두가 됩니다.

'백문은 겉보기에 불과하다'는 것으로 위의 알고리즘으로 n=2의 위의 링크 리스트를 회전시켜 보자.

구현

RotateList.java

class RotateList{

  private int getListSize(LinkedListNode head) {
    LinkedListNode curr = head;
    int listSize = 0;

    while (curr != null) {
       listSize++;
       curr = curr.next;
     }
     return listSize;
  }

  private int adjustRotatationsNeeded(int n, int length) {
    return n < 0 ? length - (n * -1) % length : n % length;
  }

   public LinkedListNode rotate_list(LinkedListNode head, int n) {

     int listSize = 0;
     listSize = getListSize(head);

     n = adjustRotatationsNeeded(n, listSize);

     if (n == 0) {
       return head;
     }

    // Find the startNode of rotated list.
    // If we have 1,2,3,4,5 where n = 2,
    // 4 is the start of rotated list

     LinkedListNode temp = head;
     int rotationsCount = listSize - n - 1;
     while(rotationsCount > 0) {
       temp = temp.next;
       rotationsCount--;
     }

     LinkedListNode new_head = temp.next;
     temp.next = null;

     LinkedListNode tail = new_head;
     while (tail.next != null) {
       tail = tail.next;
     }

     tail.next = head;
     head = new_head;

    return new_head;
  }
}