Leetcode Java Rotate List
업데이트:
문제
코드
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) {
return head;
}
ListNode temp = head;
int size = 1;
while (temp.next != null) {
temp = temp.next;
size++;
}
temp.next = head;
for (int idx = 0; idx < size - (k % size); idx++) {
temp = temp.next;
}
head = temp.next;
temp.next = null;
return head;
}
}
결과
설명
-
주어진 ListNode head를 k번 오른쪽으로 이동시킨 결과를 반환하는 문제이다.
- 아래의 두 경우에는 이동시키는 의미가 없으므로, 주어진 문제의 결과로 head를 그대로 반환한다.
- 주어진 head가 null일 경우, 이동시킬 값이 없으므로 의미가 없다.
- 주어진 k가 0일 경우, 이동시키지 않으므로 의미가 없다.
-
임시 ListNode temp를 head로 초기화 하고, 크기를 파악하기 위한 size 변수를 1로 초기화하여 선언한다.
-
temp.next가 null이 아닐 경우까지 반복하여 주어진 ListNode head의 size를 측정한다.
- temp.next에 head를 주입하고, $size - (k \mod size)$만큼 반복하여 시작 위치를 이동시킨다.
- temp를 head로 초기화 하고, temp.next에 head를 주입함으로써 temp.next부터 head 객체들의 반복으로 구성이 된다.
- 즉, temp의 값이 [5, null]에서 [5, [1, [2, [3, [4, [5, [1, [2, …]]]]]]]] 이렇게 구성이 된다.
- 그러므로 head가 반복 구성이 되므로, [1, [2, [3, [4, [5, x]]]]] 까지의 참조 값은 x부터 반복되는 객체들과 동일하다.
- temp에 temp.next값을 주입하여 시작되는 NodeList의 위치를 탐색한다.
- temp를 head로 초기화 하고, temp.next에 head를 주입함으로써 temp.next부터 head 객체들의 반복으로 구성이 된다.
-
head에 temp.next값을 넣어 시작되는 NodeList를 설정한다.
- temp.next를 null로 주입하여 5번에서 설명한 반복 구성을 제거함으로써, 종료되는 NodeList를 설정한다.
- temp.next의 값을 null로 주입하면, head에서 반복된 값의 다음 반복이 시작되는 NodeList의 next 값을 null로 설정하여 객체의 반복 구성을 제거한다.
- 6번과 7번을 통해 값이 정리된 head를 주어진 문제의 결과로 반환한다.
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기