Reverse Linked List II

---

💬 문제

[문제 링크]

연결 리스트의 시작 노드 head
구간 left ~ right의 노드를 역순으로 바꿔
연결 리스트의 시작 노드 반환

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    let curr = head;
    let prev = null;
    let i = 1;
    
    while (i < left) {
        prev = curr;
        curr = curr.next;
        i++;
    }

    let leftNode = curr;
    let leftPrev = prev;
    let next = null;

    while (i <= right) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        i++;
    }

    leftNode.next = curr;
    if (leftPrev)
        leftPrev.next = prev;
    else
        head = prev;

    return head;
};

마지막에 앞과 뒤를 연결해주기 위해 left 위치의 노드(leftNode)와
그 바로 전 노드(leftPrev)를 기억해야하기 때문에 curr를 left까지 이동
right까지 prev, curr, next를 이동하면서 curr의 next를 prev로 변경
이후 leftNode는 right 다음 노드(현재 curr)로 변경하고
leftPrev는 right 위치 노드(현재 prev)로 변경
주의할 점은 leftPrev가 null일 때 = left가 head였을 때
시작점인 head 자체를 현재의 prev로 바꾸어주어야 함

📌 결과

Accepted
Runtime 48ms (Beats 80.73%)
Memory 48.70MB (Beats 87.43%)

📚 러닝 포인트

처음에는 단순하게 값만 수정하는 방법으로 진행했었다.

var reverseBetween = function(head, left, right) {
    let curr = head;
    let value = [];
    let i = 1;
    
    while (i <= right) {
        if (i >= left)
            value.push(curr.val);
        curr = curr.next;
        i++;
    }

    curr = head;
    i = 1;

    while (i <= right) {
        if (i >= left)
            curr.val = value.pop();
        curr = curr.next;
        i++;
    }

    return head;
};

그러나 이 방법은 연결 리스트를 두번 순회해야하고, 문제에서는 one pass 알고리즘을 도전과제로 제시하고 있어 next를 수정하는 방법으로 다시 만들어봤다. 여전히 while문이 두 개라서 두번 순회하는 것처럼 보이지만, 구간이 나누어져 있어서 한 번의 순회로 볼 수 있다. 도식을 그려가면서 알고리즘을 짰는데 prev, curr, next와 기억해야할 노드 두가지까지 변수가 많아져서 조금 헷갈리긴 했다. 또 left가 head인 테스트케이스를 생각하지 못해서 한 번 늪에 빠지고, next를 다음 반복문에서 옮기지 않고 동시에 세 가지를 옮기다가 null 참조의 늪에 빠지고... 많은 고난을 겪은 후 코드를 완성할 수 있었다. 연결 리스트는 방향이 하나이다 보니 여러번의 순회 없이 뒤의 노드를 사용하기가 어렵다고 생각했는데 조금만 더 오래 생각해보면 가능하다는 것을 이번 문제로 알 수 있었다.