CS9 Linked List 유형 - 반전 처리 반전 처리연결 리스트를 반전하는 것은 흔한 인터뷰 문제이지만, 다양한 문제를 해결하는 데 사용할 수 있는 기술이기도 합니다. 이유는 포인터를 이동시키는 방법에 대한 깊은 이해를 요구하기 때문입니다. 오늘은 이것에 대해 제대로 학습해봅시다. 가정연결리스트 1 -> 2 -> 3 -> 4 가 있다고 가정하고, 이를 4 -> 3 -> 2 -> 1로 반환하고 싶다고 해봅시다. 현재 우리가 위치한 노드를 나타내는 포인터 curr이 있습니다. 처음에는 curr이 1에 위치하게 됩니다. 반전을 위해서는 2가 -> curr을 가리키도록 해야 합니다. 여기서 문제는 curr = curr.next 로 이동하면, 단일 연결리스트이기 때문에 1에 대한 참조가 사라진다는 것입니다. 이를 해결하기 위해 이전 노드를 추적하는 또 다.. 2024. 7. 22. Linked List 유형 - Fast & Slow 연결 리스트 유형의 풀이 방법 중 하나는 Fast와 Slow라는 두 개의 포인터를 사용하는 것입니다. 두 포인터는 나란히 움직이지 않고, 다른 '속도'로 이동하거나, 다른 위치에서 반복을 시작하는 등의 차이를 의미합니다. 다른 '속도'로 이동한다고 했다면, 일반적으로 Fast 포인터는 반복 당 두 노드를 이동하고, Slow 포인터는 반복 당 하나의 노드를 이동합니다. 코드를 봅시다.// head는 링크드 리스트의 첫 번째 노드를 가리킵니다.func fn(head: ListNode?) { var slow = head var fast = head // fast가 nil이 아니고 && fast.next가 nil이 아닐 때까지 while fast != nil && fast?.next !=.. 2024. 7. 21. Linked List Linked List메모리 상에 원소들을 불연속적으로 배치한 선형 자료구조불연속적인 대신 이전이나 다음 노드의 위치를 알고 있음리스트의 각 원소를 노드라고 부름노드는 데이터와 다른 노드에 대한 참조를 가짐맨 앞/뒤 노드를 head/tail 노드라고 부름어떤 노드에 대한 참조를 갖느냐에 따라 크게 3가지 종류로 나눌 수 있음 Singly Linked List각 노드는 데이터와 다음 노드에 대한 링크(참조)를 가짐 Doubly Linked List각 노드는 이전, 다음 노드에 대한 링크(참조)를 가짐 Circular Linked List마지막 노드가 헤드 노드에 대한 링크(참조)를 가짐 성질1. 헤드 노드에 대한 참조만 가지고 있기 때문에 임의의 원소에 접근/변경하려면 O(n)의 시간이 소요2. 다른 노드.. 2024. 7. 21. 이전 1 2 다음