링크드 리스트 뒤집기

Source: Dev.to

목표

• 단일 연결 리스트를 제자리(in‑place) 로 역순으로 만든다.
• 마지막 노드가 첫 번째가 된다.
• 모든 next 포인터가 역전된다.
• 역순이 된 리스트의 새로운 헤드를 반환한다.

직관

단일 연결 리스트 노드는 값과 다음 노드에 대한 참조를 저장한다.
리스트를 순회하면서 각 노드의 next 포인터를 이전 노드를 가리키도록 재할당하면 리스트가 역순이 된다.

접근법

리스트를 순회하면서 두 개의 포인터를 사용한다:

각 반복 단계에서 수행할 작업:

1. curr.next를 임시 변수(nextTemp)에 저장한다.
2. curr.next = prev 로 링크를 역전한다.
3. prev를 curr로 이동한다.
4. curr를 nextTemp로 이동한다.

curr가 null이 되면 prev가 새로운 헤드를 가리킨다.

알고리즘 (Java)

/**
 * Reverses a singly linked list in‑place.
 *
 * @param head the original head of the list
 * @return the new head after reversal
 */
Node reverseLL(Node head) {
    Node prev = null;      // will become the new head
    Node curr = head;      // current node being processed

    while (curr != null) {
        Node nextTemp = curr.next; // store next node
        curr.next = prev;          // reverse the link
        prev = curr;               // advance prev
        curr = nextTemp;           // advance curr
    }
    // prev is the new head
    return prev;
}

Note: Node는 최소한 Node next 필드를 가진 클래스로 가정한다.

예시 진행 과정

리스트 10 → 20 → 30 → 40 → null 를 고려한다.

루프가 끝난 후 prev는 40을 가리키며, 역순 리스트는 다음과 같다:

40 → 30 → 20 → 10 → null

경계 상황

• 빈 리스트: head == null → 함수는 null을 반환한다.
• 단일 노드 리스트: head.next == null → 함수는 동일한 노드를 반환한다(변경 필요 없음).

최종 출력

함수는 역순이 된 리스트의 헤드를 반환한다. 예시에서는 결과가 40이 된다.