[HackerRank 문제 풀이] Reverse a Linked List

Junu Kim·2025년 10월 1일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

27/46

Reverse a Linked List

난이도: ★★☆☆☆ • solved on: 2025-10-01

문제 요약

문제 유형: 연결 리스트(Linked List), 포인터 조작
요구사항: 단일 연결 리스트의 노드 순서를 역순으로 뒤집어 새로운 head를 반환해야 한다.

사용 개념

자료구조
- SinglyLinkedListNode (값 data, 다음 노드 참조 next)
알고리즘/기법
- 포인터 조작: prev, curr, next 세 포인터로 링크 방향을 반전
- 반복 순회(Iterative)
핵심 키워드
- 연결 반전(pointer reversal), head 갱신, 도달성(reachability), GC(garbage collection)

풀이 아이디어

문제 분해

prev(이전), curr(현재), next(다음) 포인터를 사용해 한 번에 한 노드씩 next 방향을 뒤로 바꾼다.

모든 반전이 끝나면 prev가 새 head가 된다 → prev 반환.
핵심 로직 흐름
prev = null
curr = head
while (curr != null):
    next  = curr.next     // 앞으로 진행할 발판 저장
    curr.next = prev      // 링크 반전
    prev = curr           // 한 칸 전진
    curr = next           // 다음 노드로
return prev               // 새 head
예외 처리

빈 리스트(head == null) → 그대로 null 반환

노드 1개(head.next == null) → 그대로 head 반환

입력이 2개 이상인 경우에만 head.next, head.next.next 접근 가능

코드

public static SinglyLinkedListNode reverse(SinglyLinkedListNode llist) {
    // Write your code here
    SinglyLinkedListNode prev = llist;
    SinglyLinkedListNode current = llist.next;
    SinglyLinkedListNode next = llist.next.next;
    current.next = prev;
    prev.next = null;
    while(next != null){
        prev = current;
        current = next;
        next = next.next;
        current.next = prev;
    }
    return current;
}

시간·공간 복잡도

시간 복잡도: O(N) — 각 노드를 정확히 한 번씩 방문
공간 복잡도: O(1) — 포인터 변수 3개만 추가 사용

어려웠던 점

현재 위치 인식이 헷갈림: curr(현재), curr.next(다음), prev(이전)의 역할이 머릿속에서 섞였고, LinkedList 개념이 익숙하지 않아 굳이 배열로 저장하지 않아도 괜찮다는 인식이 아직 부족했다.
다음으로 이동하면서도 반전 유지: 반전 전에 반드시 next = curr.next 백업이 필요했고, 처음에 prev에 대한 아래의 과정을 해주지 않아 무한으로 2와 1이 반복되는 오류가 발생했다.
```
current.next = prev;
prev.next = null;
```
메모리/드롭에 대한 직관
- 드롭(drop)은 실제 삭제가 아니라 “길 차단”에 가깝고, 자바/파이썬에선 더 이상 참조하지 않는 노드는 GC가 회수.
- 반전 과정 자체는 노드를 없애지 않고 next 포인터만 뒤집는 작업이라 메모리 낭비 없음.

배운 점 및 팁

3포인터 (prev, curr, next)를 항상 이 순서로 갱신:
1. next = curr.next
2. curr.next = prev
3. prev = curr
4. curr = next
에지 케이스 먼저 막기: head == null 또는 head.next == null일 때 바로 반환.
반복 vs 재귀: 반복은 명시적이고 안전 (스택 사용 X), 재귀는 간결하지만 입력 길이에 따라 스택 오버플로우 위험.
GC 직관: “누가 가리키지 않는 객체는 언젠가 사라진다.” (C/C++과 달리 가비지 컬렉터가 정의되어있는 경우 수동 삭제가 불가능하다)