leetCode (Reverse Linked List II) - linkedList

문제

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]

 

---

배경지식

• 연결리스트 : 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조
• 연결리스트 성질
  • k번 째 원소를 확인/변경하기 위해 O(k)가 필요함. (배열은 O(1)이 필요함)
  • 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1), (배열은 O(N)이 필요함)
  • 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

문제해결

범위가 주어지고, 링크드리스트를 뒤집는 문제이다. 

 

1. current 노드를 정해주자(여기서 정해지는 current노드는 left로 할 것이다.)

2. current 노드와 next 노드 뒤로 보내고, next 노드를 범위내에서 맨앞으로 바꿔준다

3. 바꾸면서 끊어졌던 연결을 다시 이어준다.

4. right-left 동안 반복 해준다

 

구현

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
 
 
 // 
//  Definition for singly-linked list.
//   @param {ListNode} head
//   @param {number} left
//   @param {number} right
//   @return {ListNode}
// 
var reverseBetween = function (head, left, right) {
    const before = { next: head };  //head 보다 앞선 node를 만들어주자.
    let prev = berfore;             //before의 다음 연결된 노드가 첫번째 노드. 여기서 prev라고 일단 정해주자
    while (--left) {               // 증감연산자를 사용해서 prev노드를 정해주자. current노드를 정해주기 위해서 prev 노드가 필요하다.
        prev = prev.next;
        --right;                    // current 노드에서 뒤집어야할 노드가 몇개인지 알기위해서 필요하다.
    }

    let current = prev.next;
    while (--right) {
        let next = current.next;
        current.next = next.next;
        next.next = prev.next
        prev.next = next;
    }

    return before.next
};