[Hackerrank] Reverse a linked list

문제 요약

문제 설명:
연결 리스트의 첫 번째 노드(head)가 주어졌을 때, 연결 리스트의 모든 노드의 방향을 뒤집어(reverse) 새로운 head를 반환하는 문제입니다.

예시:

• 입력: 1 → 2 → 3 → NULL
• 출력: 3 → 2 → 1 → NULL

---

입력 형식

1. 첫 번째 줄: 테스트 케이스 개수 ttt (1 ≤ ttt ≤ 10)
2. 각 테스트 케이스마다:
   • 첫 번째 줄: 연결 리스트의 노드 개수 nnn (1 ≤ nnn ≤ 1000)
   • 다음 n줄: 노드의 값 (1 ≤ 값 ≤ 1000)

---

출력 형식

뒤집힌 연결 리스트를 출력합니다.

---

제약 조건

• 입력값은 최대 10개의 테스트 케이스와 1,000개의 노드로 제한됩니다.
• 노드 값은 1부터 1000까지의 정수입니다.

---

해결 아이디어

1. 연결 리스트를 순회하며 next 포인터 방향을 반대로 바꿉니다.
2. prev, current, next 포인터를 사용하여 리스트를 역순으로 만듭니다.
3. 최종적으로 prev가 역순 리스트의 head가 되어 반환합니다.

---

코드 동작 결과

테스트 케이스가 모두 성공(Success) 했으며, 연결 리스트가 정상적으로 뒤집혀 출력되었습니다.

예시 입력:

 

1

5

1

2

3

4

5

예상 출력:

 

5 4 3 2 1

해당 문제에서는 llist를 연결 리스트의 head 노드로 준다. 그래서 llist가 존재하는 동안 반복문을 이용해서 각 노드의 next 포인터를 previous node로 바꾸어 주면 된다.

먼저 현재 노드의 next node를 미리 저장하고, 현재 노드의 next를 이전 노드로 연결한다. 그리고 현재 노드와 이전 노드를 한 칸씩 이동시키며 리스트의 방향을 반대로 바꾸어주면 된다. 코드는 다음과 같다.

def reverse(llist):
    prev = None
    while llist:
        next_node = llist.next
        llist.next = prev
        prev = llist
        llist = next_node
    return prev