연결 리스트

1 → 2 → 3을 뒤집어 3 → 2 → 1로 만드는 과정을 손으로 따라가 봅니다. 손가락 두 개만 씁니다 — prev(이미 뒤집은 부분의 맨 앞)와 cur(지금 보고 있는 쪽지)입니다.

주목할 곳은 "다음을 먼저 적어 둔다" 입니다. 화살표를 먼저 돌려 버리면 남은 쪽지들이 어디 있는지 알 방법이 사라집니다. 종이에 그려 보면 이 한 줄의 순서가 왜 절대적인지 바로 보입니다.

노드는 값과 다음 노드를 가리키는 포인터로 이루어집니다.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

1. 손가락 두 개를 준비합니다. 뒤집은 부분의 맨 앞은 처음에 아무것도 없으므로 null입니다.

let prev: ListNode | null = null;
let cur = head;

2. 현재 노드가 있는 동안 반복하며, 다음 노드를 먼저 저장합니다. 이것을 빠뜨리면 나머지 사슬을 잃습니다.

while (cur !== null) {
  const next = cur.next; // 반드시 화살표를 돌리기 전에
}

3. 화살표를 뒤로 돌립니다.

cur.next = prev;

4. 두 손가락을 한 칸씩 전진시키고, 끝나면 prev를 새 head로 반환합니다.

prev = cur;
cur = next;

전체 코드 — "연결 리스트 뒤집기":

function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur !== null) {
    const next = cur.next; // ① 다음을 미리 저장 (안 하면 사슬을 잃는다)
    cur.next = prev;       // ② 화살표를 뒤로 돌리고
    prev = cur;            // ③ 두 포인터 전진
    cur = next;
  }
  return prev; // 새 head
}

노드를 한 번씩만 지나가므로 O(N)이고, 추가로 쓰는 메모리는 손가락 세 개뿐이라 O(1)입니다.

• 입력이 배열이 아니라 head 노드 하나로 주어지면 그 자체가 신호입니다 — 길이도 인덱스도 주어지지 않습니다.
• "리스트를 뒤집어라 / 두 정렬 리스트를 하나로 합쳐라 / 뒤에서 K번째 노드를 지워라 / 사이클이 있는지 판단하라" — 코테 단골 문장입니다.
• 대표 상황: 두 정렬 리스트 병합, K번째 뒤 노드 제거, 회문 리스트 판정.
• 실무에서는 LRU 캐시(해시 + 이중 연결 리스트) 같은 조합 구조의 부품으로 등장합니다.

코테에서 연결 리스트 문제는 자료구조 자체보다 포인터를 잃지 않고 조작하는 정확성 을 봅니다.

1) 뒤집기 (prev·cur 두 포인터) — "아주 작은 예시"와 "단계별로 이해하기"의 그 과정입니다.

function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur !== null) {
    const next = cur.next; // ① 다음을 미리 저장 (안 하면 사슬을 잃는다)
    cur.next = prev;       // ② 화살표를 뒤로 돌리고
    prev = cur;            // ③ 두 포인터 전진
    cur = next;
  }
  return prev; // 새 head
}

2) 빠른/느린 포인터 (runner) — 중간 찾기·사이클 감지

// slow는 1칸, fast는 2칸 — fast가 끝에 닿으면 slow가 중간
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
  slow = slow!.next;
  fast = fast.next.next;
}
// 사이클 감지: fast === slow가 되면 사이클 존재 (플로이드)

3) 더미(dummy) 헤드 — head가 바뀔 수 있는 삽입·삭제·병합

const dummy = new ListNode(0, head);
let tail = dummy;
// ...tail.next를 조작...
return dummy.next; // head가 삭제·교체돼도 안전

• cur.next = prev를 먼저 하고 다음 노드를 저장 안 함 — 사슬이 끊겨 나머지를 잃습니다 (패턴 1의 ①이 반드시 먼저)

cur.next = prev;
const next = cur.next;   // 이미 prev를 가리킴 — 뒤쪽 노드를 영영 잃음
 
const next2 = cur.next;  // 저장이 먼저
cur.next = prev;

• fast.next.next 접근 전에 fast.next null 확인 누락 — 런타임 에러의 90%

while (fast !== null) { fast = fast.next.next; }             // fast.next가 null이면 터짐
while (fast !== null && fast.next !== null) { fast = fast.next.next; }

• head 자체가 삭제되는 경우를 따로 처리하다 코드가 꼬임 — 더미 헤드로 통일
• 병합에서 남은 꼬리를 붙이는 것을 잊음 (tail.next = l1 ?? l2)

• 배열과의 비용 차이가 나는 이유: 배열은 메모리에 연속으로 놓여 있어 arr[i]의 주소를 곱셈 한 번으로 계산하지만(O(1)), 그 연속성을 지키려 중간 삽입·삭제 때 뒤 원소를 전부 밀어야 합니다(O(N)). 연결 리스트는 노드가 메모리에 흩어져 있어 인덱스로 바로 접근할 수 없지만(O(N)), 중간 삽입·삭제가 포인터 조작만으로 O(1) 입니다. 단, "그 자리까지 찾아가는" 비용은 별도라는 점을 잊지 마세요.
• 플로이드 사이클 판정이 왜 맞는가: 사이클이 있으면 빠른 포인터가 느린 포인터보다 한 바퀴 이상 앞서게 되고, 둘의 간격이 매 걸음 1씩 줄어들므로 반드시 정확히 겹칩니다. 사이클 시작점까지 구하려면 만난 지점에서 포인터 하나를 head로 되돌리고 둘을 1칸씩 움직여 다시 만나는 곳을 보면 됩니다.
• 재귀로 뒤집기: const newHead = reverse(head.next); head.next.next = head; head.next = null; 형태로도 되지만 노드 수만큼 콜 스택을 쓰므로(O(N) 메모리), 입력이 큰 코테에서는 반복문 버전이 안전합니다.
• 이중 연결 리스트: prev 포인터를 하나 더 두면 어떤 노드든 앞뒤로 오갈 수 있어 "임의 노드를 O(1)에 제거"가 가능해집니다. LRU 캐시가 해시(위치 찾기)와 이중 연결 리스트(순서 조작)를 붙여 쓰는 이유입니다.

시각화로 뒤집기의 포인터 이동을 눈에 익힌 뒤, 뒤집기 → 중간 찾기 → 병합 → 사이클 순으로 푸세요. 종이에 노드와 화살표를 그리면서 푸는 습관이 가장 빠른 지름길입니다.