JavaScript의 연결 목록 주기 — LeetCode 141, 142.

Feb 24 2023

LeetCode를 하다가 141번 문제에 봉착했다. Linked List 데이터 구조가 존재하지 않는 자바스크립트를 주 프로그래밍 언어로 사용하다 보니 아이디어를 파악하고 해결책을 찾는데 애를 먹었다.

LeetCode를 하다가 141번 문제에 봉착했다. Linked List 데이터 구조가 존재하지 않는 자바스크립트를 주 프로그래밍 언어로 사용하다 보니 아이디어를 파악하고 해결책을 찾는데 애를 먹었다. LeetCode에는 JavaScript용 Linked List 구현이 내장되어 있으며 솔루션만 작성하면 됩니다. 그래서 나는 같은 문제에 직면할 수 있는 다른 사람들을 위해 더 쉽게 만들면 어떨까 생각했습니다. 이 기사는 몇 가지 개념을 이해하는 데 도움이 될 수 있으므로 끝까지 읽으십시오. 뻔한 질문으로 시작합시다…

연결된 목록이란 무엇입니까?

연결된 목록은 배열과 유사한 선형 데이터 구조입니다. 그러나 배열과 달리 요소는 특정 메모리 위치나 인덱스에 저장되지 않습니다. 오히려 각 요소는 해당 목록의 다음 개체에 대한 포인터 또는 링크를 포함하는 별도의 개체입니다.

각 요소(일반적으로 노드라고 함)에는 저장된 데이터와 다음 노드에 대한 링크라는 두 가지 항목이 포함되어 있습니다. 데이터는 유효한 데이터 유형이 될 수 있습니다. 아래 다이어그램에서 이를 확인할 수 있습니다.

연결된 목록

JavaScript에서는 다음과 같이 표시됩니다.

const list = {
    head: {
        data: 6
        next: {
            data: 10                                             
            next: {
                data: 12
                next: {
                    data: 3
                    next: null	
                    }
                }
            }
        }
    }
};

class ListNode {
    constructor(data, next = null) {
        this.data = data
        this.next = next               
    }
}

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

function getLinkedList (arr){
  const head = arr.reverse().reduce((a,b) => {
  if (!a) {
    a = new ListNode(b);
  } else {
    a = new ListNode(b, a);
  }
  return a;
}, null);

return new LinkedList(head);
}

const list = getLinkedList([2,5,1,7])
console.log(list.head)
// ListNode { data: 2, next: ListNode { data: 5, next: ListNode { data: 1, next: [ListNode] } }}
console.log(list.head.next.data)
// 5

연결 목록 주기란 무엇입니까?

연결된 목록이 더 이상 시작과 끝이 있는 선형이 아닌 경우 순환이 발생합니다 . 대신 노드 루프를 순환합니다.

연결 리스트 주기

꼬리 노드의 다음 노드가 목록의 다른 노드를 가리키도록 하여 이를 달성할 수 있습니다. 주기가 위치 2에서 시작하기를 원한다고 가정해 보겠습니다. 다음을 수행하여 이를 달성할 수 있습니다.

let tail = head
// get the tail
while(tail.next) {
   tail = tail.next
}

// get the cycle node
let pos = 2;
let cycleNode = head
while(pos > 0 && cycleNode.next) {
    cycleNode = cycleNode.next
    pos--
}
// point the next of tail to cycle node
tail.next = cycleNode;

토끼와 거북이

연결 리스트에서 순환을 확인하는 문제는 처음에는 겁이 날 수 있지만 Floyd의 Tortoise and Hare 알고리즘을 사용하면 쉽게 이해하고 해결할 수 있습니다. 아이디어는 "거북이"와 같은 느린 포인터와 "토끼"와 같은 빠른 포인터를 사용하는 것입니다. 거북이 e는 0 위치에서 시작하고 토끼는 1 위치에서 시작합니다. 거북이가 한 번에 한 칸씩 움직이고 토끼가 한 번에 두 칸씩 움직인다면, 그들은 결국 한 주기의 어떤 장소에서 만나게 됩니다. 각각의 움직임을 그려서 확인할 수 있습니다.

꼬리가 목록의 두 번째 노드를 가리키는 길이의 연결 목록에서 순환을 상상해 봅시다.

토끼와 거북이: 시작

토끼와 거북이: 진보

토끼와 거북이: 만나다

다음은 JavaScript에서 구현해야 하는 알고리즘입니다.

create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
       move the slow pointer by one node and fast pointer by two nodes
       if: at any time, slow pointer equals fast pointer
          linked list contains a cycle.

function hasCycle (head) {
// create 2 pointers
let slow = head;
let fast = head;

while(fast && fast.next){ // while pointers exist and fast pointer has a next value
    fast = fast.next.next; // move fast pointer by two nodes
    slow = slow.next; // move slow pointer by one node
    if(fast === slow) return true; // linked list has a cycle
    }

return false;
}

당신의 초기 생각은 토끼와 거북이가 만나는 노드를 반환하자는 것일 수 있습니다. 하지만 위의 그림에서 볼 수 있듯이 주기는 두 번째 노드에서 시작되고 토끼와 거북이는 세 번째 노드에서 만납니다. 그래서 작동하지 않습니다.

솔루션에는 세 번째 포인터가 필요합니다. 토끼와 거북이가 만나는 노드, 즉 빠른 포인터가 느린 포인터와 같은 노드를 찾은 후 느린 포인터와 세 번째 포인터를 한 노드씩 계속 이동하면 결국 사이클이 시작되는 지점에서 만나게 됩니다. JavaScript에서 구현해야 하는 알고리즘은 다음과 같습니다.