3. Linked List

링크드 리스트란?

포인터로 연결된 노드들의 컬렉션이라고 할 수 있고, 스택, 큐, 해시 테이블을 구현하는데 사용될 수 있다. 시작 지점에 노드를 추가하거나 삭제하는 것은 O(1) 상수 시간이 소요된다. 

 

노드 클래스 코드 예시

public class Node {
    int val;
    Node next;
    ListNode() {}
    Node(int val) {
        this.val = val;
    }
    Node(int val, Node next) {
    	this.val = val;
        this.next = next;
    }
}

 

코딩테스트 팁 🗝️

Recursion도 알아야 하고 그 어렵다는 포인터를 활용해서 문제를 풀어야 하기 때문에 그림을 많이 그려보면서 코드를 따라가 보는 것이 중요하다. 만약 Easy 문제도 너무 어렵게 느껴진다면 재귀나 다른 문제들을 풀면서 시간이 좀 지난 다음에 보면 이해가 더 잘 될 수도 있으니 막히면 잠깐 쉬었다 가는 것도 좋은 방법이다. 

Runner Technique 
🎃 링크드 리스트 문제에서 많이 활용
🎃 slow and fast pointer

Recursion
🎃 재귀를 사용할 경우, Space Complexity는 O(n) 인데
🎃 여기서 n은 재귀의 깊이를 뜻한다

 

코드

💧 slow/fast 포인터 사용 시 while문 조건 작성법

slow, fast 포인터를 사용해서 문제를 푸는 경우, 예를 들어 리트코드 141번 문제 Linked List Cycle은 slow 포인터를 한칸씩, fast 포인터를 두칸씩 옮기다가 둘이 만나면 해당 링크드 리스트에 싸이클이 있다고 알 수 있는데 이때 코드는 다음과 같다. 

링크드 리스트에 싸이클이 있는지 확인하는 코드

여기서 while문에 fast가 null이 아닐때 그리고 fast.next가 null이 아닐때를 break 조건으로 작성해 줘야한다. 왜냐면 싸이클이 없는 linear한 링크드 리스트일 경우에는 while loop을 빠져나와야 하는데 이때 링크드 리스트의 노드의 갯수가 홀수일때와 짝수일때를 고려해야 하기 때문이다. 

한칸씩 움직이는 slow보다 fast가 항상 더 앞에 가기 때문에 fast 포인터를 확인해야 하고 그림에서와 같이 짝수일 경우는 fast 포인터가 null이 되지만 홀수일 경우에는 fast.next가 null인지를 확인해야 NullPointerException 에러 없이 링크드 리스트를 순회할 수 있다. 

 

💧 Reverse Linked List 

Linked list를 reverse하려면 결국 기존 노드의 next가 다음 노드가 아니라 이전 노드를 가르키도록 바꿔줘야 하고 recursive, iterative 방법 두가지로 코드를 작성할 수 있다. 

 

Recursive 방법

1. base case: 링크드 리스트가 empty거나 한개의 노드만 가지고 있다면 이미 reversed 된 상태임으로 head를 리턴

2. base case가 아니면 재귀적으로 reverse linked list 함수 호출 (reverseList(head.next))

3. 새로운 헤드에 대한 참조 저장 (ListNode newHead = reverseList(head.next))

4. reverse linked list (head.next.next = head)

5. 순환참조를 방지하기 위해 다음 포인터의 연결을 널로 끊어줌 (head.next = null)

6. 새로운 헤드 리턴 (return newHead)

reverse linked list recursive way

 

 

reverse linked list하는 부분인 head.next.next = head가 이해가 잘 안되면, head.next를 중간에 한번 front 변수로 저장하고 front의 다음이 head를 가르킬 수 있게 작성할 수도 있다.  

head.next의 next 포인터가 head를 볼 수 있도록 바꿔줘야 reverse 할 수 있다

 

 

Iterative 방법

1. temp 포인터를 선언한 뒤 head에 위치해서 링크드 리스트를 순회하는데 사용

2. prev 포인터를 null로 생성한 다음 이전 노드를 트랙하는데 활용. next 포인의 방향을 바꾸는데 사용

3. temp 포인터를 이동하면서 링크드 리스트 전체를 순회. temp 포인터가 null일 경우 순회 종료

4. temp 포인터가 다음으로 이동할 노드의 참조를 잃지 않기 위해 temp.next를 수정하기 전에 front 포인터에 저장

5. temp 포인터가 prev를 가리키도록 수정

----- next iteration을 수행하기 위해 prev, temp 위치를 한칸씩 이동 ----

6. prev를 현재 노드로 이동

7. temp 포인터를 front 포인터로 이동

8. temp가 널이 되면 reversed linked list의 새로운 head인 prev 포인터 리턴

reverse linked list iterative way

 

링크드 리스트 문제

LeetCode

206. Reverse Linked List (iterative하고 recursive 방법 두가지로 풀어봐야함)

876. Middle of the Linked List (fast and slow pointer 활용. Tortoise and Hare 알고리즘)

21.Merge Two Sorted Lists (이것도 iterative/recursive 방법 두가지로 풀어봐야 하고 이미 정렬이 되어 있기 때문에 투포인터 개념을 활용해서 머지하면 될 것 같지만 next pointer를 변경해줘야 해서 Easy 문제이지만 생각보다 어려움 ★★★)

19. Remove Nth Node From End of List (fast/slow pointer 활용. fast 포인터를 n 노드 앞에 위치한 다음 slow/fast 포인터를 1씩 움직이면, fast 포인터가 가장 마지막 노드에 있을 때 slow 포인터는 마지막 노드에서 nth노드 앞에 위치)

2. Add Two Numbers (만약에 새로운 노드 리스트를 만들어야 한다면 dummy node 활용하면 코드가 깔끔해짐. int carry 변수를 선언해서 10 정보 저장)

237. Delete Node in a Linked List (문제 설명이 명확하지 않을 수 있는데 리트코드 디스커션에 Best로 정렬했을 때 나오는 맨 처음 글을 참고하면 인사이트를 얻을 수 있음. "no one can delete the node correctly without access to its predecessor")

160. Intersection of Two Linked Lists (리스트의 길이를 구해서 풀 수도 있지만 두개의 더미 노드를 헤드에 위치한 다음 리스트 순회. null일 때 해당 노드를 반대 리스트의 헤드에 위치한 다음 두개의 더미 노드가 만날 때까지 순회)

141. Linked List Cycle (slow/fast 포인터를 사용하는 가장 기본적인 문제)

25. Reverse Nodes in k-Group (링크드 리스트를 reverse 하는 방법, 재귀를 알고 있어야 풀 수 있음 ★★★★)

234. Palindrome Linked List (중간 노드를 찾아서 두번째 부분을 reverse. 포인터의 위치가 헷갈릴 수 있으므로 그림으로 그려봐야함)

142. Linked List Cycle 2 (141번의 심화 버전. 우선 cycle이 있는지 찾고, slow포인터는 starting point에, fast 포인터는 collision point에 위치한 뒤 한개씩 이동하다가 둘이 만나는 곳이 starting 포인트인데 이것에 대한 설명은 takeUForward 동영상에 잘 나와있음)

61. Rotate List (배열문제에서도 그렇지만 k번을 rotate하라는 문제가 나오면 % modulo를 사용해야함. 이 문제에서는 recursion를 사용하기 때문에 그냥 k번 회전하면 StackOverflowError가 뜸)

138. Copy List with Random Pointer (deep copy해야함. 해시맵을 사용해서 풀어도 되는데  Space Complexity를 O(1)로 줄이려면 새로 만든 노드를 기존 노드 리스트 순서 사이사이에 위치해서 풀 수 있음)

1171. Remove Zero Sum Consecutive Nodes from Linked List (prefix sum과 hashmap 사용)

 

 

참고자료

도서: 코딩 인터뷰 완전분석

https://takeuforward.org/data-structure/reverse-a-linked-list/

https://arminnorouzi.github.io/posts/2023/06/blog-post-3/

https://www.youtube.com/watch?v=2T-A_GFuoTo&t=650s

https://github.com/jwasham/coding-interview-university?tab=readme-ov-file#linked-lists