Leetcode

[Leetcode] 92. Reverse Linked List II - JS

Wix 2024. 11. 5. 10:00

https://leetcode.com/problems/reverse-linked-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

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와 연결될 수 있다.