[LeetCode] Reverse Linked List

🧑‍💻 언어 및 제출 결과

• 사용 언어: TypeScript
• 통과 여부: ✅

🧠 풀이 설명

첫 번째 풀이

function reverseList(head: ListNode | null): ListNode | null {
  let curr: ListNode | null = head;
  let prev: ListNode | null = null;
  while (curr) {
    [curr.next, curr, prev] = [prev, curr.next, curr];
  }
  return prev;
}

의식의 흐름대로 구조 분해를 사용하여 작성했습니다
거꾸로 뒤집는 것을 한 단계씩 밟아 그려 보면

1. 현재 노드의 화살표를 뒤집기 curr.next = prev 현재 노드가 이전 노드를 가리키도록 변경
2. 현재 포인터를 다음으로 이동 curr = curr.next (원래 다음 노드) 다음 노드로 이동해서 계속 처리
3. 이전 포인터를 현재로 업데이트 prev = curr (원래 현재 노드) 다음 반복에서 사용할 이전 노드로 설정

위 동작이 동시 실행됩니단

현재가 null이면 리스트는 끝이 나니 종료 조건을 주고 다음, 현재, 이전 값을 치환해줍니다

말로 설명이 어려으ㅓ서 아래 세 번째 풀이에 과정을 더 자세하게 나타내는 코드 작성 해놨습니다

---

두 번째 풀이

const reverseList = (head: ListNode | null, prev: ListNode | null = null): ListNode | null => head ? reverseList(head.next, Object.assign(head, { next: prev })) : prev;

이건 그냥 재미로.. 성능 박살났습니다.

head가 null일 때까지 head와 prev를 재귀로 넘기면서 매 단계마다 Object.assign을 써서 head.next를 prev로 덮어 씌우고
그 head를 다음 prev로 넘깁니다

즉, 한 줄로 다음 두 가지를 동시에 합니다

1. 방향을 뒤집고 (head.next = prev)
2. 뒤집힌 head를 다음 재귀의 prev로 넘김

이걸 head가 null일 때까지 쭉 반복하면 prev는 결국 완전히 역순으로 뒤집힌 리스트의 첫 번째 노드가 됩니다.

참고로 Object.assign이 불변처럼 생겼지만 실제로는 직접 head를 수정하기 때문에 기존 노드를 건드리는 구조입니다 (얌전한 척하면서 원본 바꿔버림)

재귀 깊이는 리스트 길이만큼 쌓이고 Object.assign도 매 호출마다 객체 병합이 일어나므로, 코드가 짧은 대신 런타임과 메모리 성능은 초 박살 납니다.

---

세 번째 풀이

function reverseList(head: ListNode | null): ListNode | null {
  let curr: ListNode | null = head;
  let prev: ListNode | null = null;

  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  return prev;
}

reverse 시키는 것은 head의 next 값들을 현재 값의 이전으로 하나하나 보내져야 뒤집힙니다
현재 값은 포인터가 되기 떄문에 curr(pointer)를 만들어 주었고 이전 값을 저장 할 prev를 만들었습니다

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

그 다음 생각한 건 리스트를 순회하면서 각 노드의 방향을 하나씩 반대로 바꿔주면 되지 않을까였습니다
예를 들어 1 → 2 → 3 → 4 → 5 라는 리스트가 있을 때,

curr = 1, prev = null, next = 2
1 => 2 => 3 => 4 => 5 => null
한번 뒤집는다면
curr = 2, prev = 1, next = 3
2 => 1 => 3 => 4 => 5 => null
두번 뒤집는다면
curr = 3, prev = 2, next = 4
3 => 2 => 1 => 4 => 5 => null
세번 뒤집는다면
curr = 4, prev = 3, next = 5
4 => 3 => 2 => 1 => 5 => null
네번 뒤집는다면
curr = 5, prev = 4, next = null
5 => 4 => 3 => 2 => 1 => null
이렇게 되면 모두 뒤집히게 되지요

1의 next를 null로 만들고, 2의 next를 1로, 3의 next를 2로 ... 이런 식으로 연결을 뒤집는 구조로..

   // 수정 전
  while (curr) {
    curr.next = prev;
    prev = curr;
    curr = curr.next;
  }

하지만 문제는 연결을 바꾸는 순간, 기존의 다음 노드를 잃어버려 순회가 끊겼습니다
예를 들어 curr가 2일 때 curr.next를 이전 노드로 돌려버리면 그 다음 처리할 노드(3)에 접근할 방법이 사라지기 때문에
next라는 임시 포인터를 하나 더 두고 이 포인터는 현재 노드(curr)의 다음 노드를 미리 백업해두는 용도로 사용했습니다
curr.next를 변경한 뒤에도 다음 노드(next)를 따라가면 리스트를 끊김 없이 순회할 수 있습니다

  // 수정 후
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

전체적으로는 curr가 리스트를 앞으로 따라가고 prev가 뒤에서부터 하나씩 연결을 되돌리며 따라가는 구조로 설계했고
이 과정을 반복하면서 curr가 끝(null)까지 가면 prev가 역순으로 바뀐 리스트의 head가 되므로 그걸 반환하면 됩니다

아래 코드는 위 과정을 시각화 한 코드입니다 돌려보시면 이해가 빠르게 될 것 같습니다.

class ListNode {
  val: number;
  next: ListNode | null;

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

const node_1 = new ListNode(1);
const node_2 = new ListNode(2);
const node_3 = new ListNode(3);
const node_4 = new ListNode(4);
const node_5 = new ListNode(5);

node_1.next = node_2;
node_2.next = node_3;
node_3.next = node_4;
node_4.next = node_5;

function reverseList_test(head: ListNode | null): ListNode | null {
  let curr: ListNode | null = head;
  let prev: ListNode | null = null;
  let step = 0;

  console.log("== 연결 리스트 뒤집기 시작 ==");
  console.log("초기 head 상태:", JSON.stringify(head, null, 2));

  while (curr) {
    const next = curr.next;

    console.log("--------------------------------");
    console.log(`${++step}회전`);
    console.log(`curr: ${curr.val}`);
    console.log(`prev: ${prev ? prev.val : "null"}`);
    console.log(`next: ${next ? next.val : "null"}`);

    curr.next = prev;

    prev = curr;
    curr = next;

    // 현재까지 뒤집힌 리스트 구조를 출력
    console.log("뒤집힌 현재 리스트 상태 (prev 기준):");
    console.log(JSON.stringify(prev, null, 2));
  }

  console.log("--------------------------------");
  console.log("최종 결과:");
  console.log(JSON.stringify(prev, null, 2));

  return prev;
}

reverseList_test(node_1)

결과

== 연결 리스트 뒤집기 시작 ==
초기 head 상태: {
  "val": 1,
  "next": {
    "val": 2,
    "next": {
      "val": 3,
      "next": {
        "val": 4,
        "next": {
          "val": 5,
          "next": null
        }
      }
    }
  }
}
--------------------------------
1회전
curr: 1
prev: null
next: 2
뒤집힌 현재 리스트 상태 (prev 기준):
{
  "val": 1,
  "next": null
}
--------------------------------
2회전
curr: 2
prev: 1
next: 3
뒤집힌 현재 리스트 상태 (prev 기준):
{
  "val": 2,
  "next": {
    "val": 1,
    "next": null
  }
}
--------------------------------
3회전
curr: 3
prev: 2
next: 4
뒤집힌 현재 리스트 상태 (prev 기준):
{
  "val": 3,
  "next": {
    "val": 2,
    "next": {
      "val": 1,
      "next": null
    }
  }
}
--------------------------------
4회전
curr: 4
prev: 3
next: 5
뒤집힌 현재 리스트 상태 (prev 기준):
{
  "val": 4,
  "next": {
    "val": 3,
    "next": {
      "val": 2,
      "next": {
        "val": 1,
        "next": null
      }
    }
  }
}
--------------------------------
5회전
curr: 5
prev: 4
next: null
뒤집힌 현재 리스트 상태 (prev 기준):
{
  "val": 5,
  "next": {
    "val": 4,
    "next": {
      "val": 3,
      "next": {
        "val": 2,
        "next": {
          "val": 1,
          "next": null
        }
      }
    }
  }
}
--------------------------------
최종 결과:
{
  "val": 5,
  "next": {
    "val": 4,
    "next": {
      "val": 3,
      "next": {
        "val": 2,
        "next": {
          "val": 1,
          "next": null
        }
      }
    }
  }
}

 📊 시간/공간 복잡도

첫 번째 풀이

• 시간 복잡도: O(n)
  각 반복문에서 구조 분해 할당으로 3개의 변수 치환이 있지만, 모두 O(1) 연산
  총 노드 수가 n개면 n번만 반복함
• 공간 복잡도: O(1)
  추가적인 메모리는 curr, prev, 구조 분해에 쓰이는 임시 포인터뿐

---

두 번째 풀이

• 시간 복잡도: O(n)
  각 노드를 한 번씩 재귀 호출로 처리함 => O(n)
• 공간 복잡도: O(n)
  재귀 호출이 깊이 n만큼 쌓임 => 콜스택이 n단계 필요

---

세 번째 풀이

• 시간 복잡도: O(n)
  노드 하나당 한 번씩만 순회 전체 노드 수가 n이면 O(n)
• 공간 복잡도: O(1)
  curr, prev, next 세 개의 포인터만 사용되고 노드 자체는 재사용되고 새로 생성된 노드는 없음

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.

첫 번째 풀이

두 번째 풀이

세 번째 풀이