[재귀,반복문] LeetCode 206번 문제 학습

문제 설명

Reverse Linked List는 단일 연결 리스트(Singly Linked List)를 뒤집는 문제임. 리스트의 노드 순서를 완전히 반대로 만들어서 새 헤드를 리턴해야 함.

• 입력: 1 -> 2 -> 3 -> 4 -> 5 → 출력: 5 -> 4 -> 3 -> 2 -> 1.
• 입력: 1 (노드 하나) → 출력: 1.
• 입력: nil (빈 리스트) → 출력: nil.

제약 조건:

• 리스트 노드 수는 0 이상.
• 노드 값은 정수(int).
• 연결 리스트는 ListNode 구조체: Val (값), Next (다음 노드 포인터).
• 시간복잡도 O(n), 공간복잡도 O(1)로 푸는 게 이상적.

문제를 푼 과정

1. 기저 사례 (Base Case):
   • head == nil이면 빈 리스트라 바로 head 리턴. 아무 작업 안 해도 됨.
   • 이 조건으로 빈 리스트 케이스 처리.
2. 투 포인터로 리스트 뒤집기:
   • 세 포인터 사용:
     • prev: 이전 노드 (초기값 nil).
     • cur: 현재 노드 (초기값 head).
     • cur_next: 다음 노드 (임시 저장용).
   • for cur != nil 루프에서:
     • cur_next := cur.Next: 다음 노드 저장 (연결 끊기 전에 미리).
     • cur.Next = prev: 현재 노드의 Next를 이전 노드로 반전.
     • prev = cur: prev를 현재 노드로 갱신.
     • cur = cur_next: cur를 다음 노드로 이동.
   • 이 과정으로 노드 연결 방향을 하나씩 반대로 바꿈.
   • 예: 1 -> 2 -> 3에서 첫 루프 후 1 -> nil, prev = 1, 다음 루프에서 2 -> 1, 이런 식.

---

어떤 알고리즘 썼는지

이 문제는 연결 리스트 조작이 핵심임. 

1. 투 포인터 (Two Pointers)
   • prev, cur, cur_next로 리스트 순회하면서 연결 반전.
   • 각 노드의 Next 포인터를 이전 노드로 바꾸는 방식.
   • 시간복잡도 O(n), 공간복잡도 O(1).
2. 반복(Iterative)
   • 리스트를 한 번 순회하면서 연결 뒤집음.
   • 재귀 대신 반복 써서 스택 메모리 안 씀. 최적화 잘 됨.

대안 접근법

• 재귀(Recursion): 재귀로도 뒤집을 수 있음. 근데 스택 메모리 O(n) 쓰고 코드가 살짝 복잡.
• 스택(Stack): 모든 노드 스택에 넣고 꺼내면서 새 리스트 만들기. 시간 O(n), 공간 O(n). (처음에 이렇게 했다가, 수정하였음 )
• 반복 투 포인터가 시간/공간 모두 최적이라 지금 방식이 최고임.

package main

import (
	"fmt"
)

type ListNode struct {
    Val int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	prev := &ListNode{}
	prev = nil
	cur := head

	for cur != nil {
		cur_next := cur.Next
		cur.Next = prev
		prev = cur
		cur = cur_next
	}

	return prev
}

func main() {
	// Node -> [1, 2, 3, 4, 5] Create the variable
	a := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
	b := reverseList(a)
	printListNode(b)
}

func printListNode(a *ListNode) {
	for a != nil {
		fmt.Println(a)
		a = a.Next
	}
}