Leetcode
[Leetcode] 92. Reverse Linked List II - JS
Wix
2024. 11. 5. 10:00

1. 문제 분석
문제분석
--------------------
단일 연결 리스트의 헤드와 두 개의 정수 left 및 right가 주어지면
left <= right인 경우
리스트의 노드를 왼쪽 위치에서 오른쪽 위치로 반전하고 반전된 리스트를 반환합니다.
제한조건
--------------------
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
2. 접근 방법
접근방법
--------------------
dummy 노드를 만들어서 head 앞에 연결해준다.
결과값으로 dummy.next를 반환한다.
prev = left 이전에 위치한 노드
left 까지 prev 노드를 이동시킨다.
curr = left 인덱스에 위치한 노드
next = null 초기화
left ~ right 구간만큼 curr, next, prev를 재배치한다.
- next 할당
- curr.next 갱신
- next.next 갱신
- prev.next 갱신
dummy.next 반환
3. 코드
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var reverseBetween = function(head, left, right) {
const dummy = new ListNode();
dummy.next = head;
let prev = dummy;
for (let i = 1; i < left; i++) {
prev = prev.next;
}
let curr = prev.next;
let next = null;
for (let i = 0; i < right - left; i++) {
next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next
};
4. 복잡도 분석
- 시간복잡도: O(n)
- 공간복잡도: O(1)
전체 연결 리스트를 역순하는 방법을 구간만 역순하는 문제에 적용하려하니 적절하지 않았던 것 같다.
1 -> 2 -> 3 -> 4 -> 5, left = 2, right =4 예시에서 처음에 생각한 방법은
1 -> 3 -> 2 -> 4 -> 5 로 '2'와 '3'을 역순 시키고 1 -> 3 -> 4 -> 2 -> 5 로 '2'와 '4'를 역순 시키는 방법을 적용했다.
보다 시피 결과가 이상하게 나온다.
GPT에게 물어보면 공부한 결과,
left ~ right 구간에서
1 -> 2 -> 3 -> 4 -> 5
- 첫번째 역순 시 1 -> 3 -> 2 -> 4 -> 5 prev = 1, curr = 2, next = 3
- 두번째 역순 시 1 -> 4 -> 3 -> 2 -> 5 prev = 1, curr = 2, next = 4
코드에서도 알 수 있듯이, prev, curr 변수는 갱신되지 않고 next 포인터만 바꿔주고 있다.
prev 변수는 역순 시작하는 구간 이전의 노드를 유지해줘야지만 next 포인터로 역순된 구간의 head와 연결될 수 있다.