[Hackerrank] Reverse a doubly linked list

Doubly Linked List 뒤집기 문제 요약 (HackerRank)

---

문제 설명

주어진 이중 연결 리스트(Doubly Linked List)의 head 노드 포인터를 기준으로 리스트의 순서를 반대로 뒤집는 문제입니다.
즉, 각 노드의 next와 prev 포인터를 서로 교환하여 리스트의 방향을 반전시키고, 뒤집힌 리스트의 head 노드를 반환해야 합니다.

---

입력 형식

1. 첫 번째 줄에 테스트 케이스 개수 ttt가 주어집니다. (1 ≤ t ≤ 10)
2. 각 테스트 케이스마다:
   • 첫 번째 줄에 노드의 개수 n이 주어집니다. (0 ≤ n ≤ 1000)
   • 다음 n 줄에 노드의 데이터 값이 주어집니다. (0 ≤ 데이터 ≤ 1000)

---

출력 형식

• 뒤집힌 연결 리스트의 head 노드를 반환합니다.
• 프로그램은 리스트의 데이터를 공백으로 구분하여 출력합니다.

---

제약 조건

• 리스트가 비어 있을 수도 있습니다. (즉, head가 NULL일 수 있음)
• 노드의 데이터 값은 0 이상 1000 이하의 정수입니다.

문제 예시

입력:

1

4

1

2

3

4

출력:

 

4 3 2 1

 

이 문제는 바로 어제 풀었던 reverse a linked list랑 매우 유사하다. 차이점은 어제 문제는 반복문을 이용해 next node만 바꾸어주었다면, 오늘은 double linked list이니 양 쪽으로, prev node와 next node를 둘 다 바꾸어 주어야 한다. 어제와 동일하게 llist를 head node로 주니 current가 존재하는 동안 current의 next_node를 미리 저장해 두고 next와 prev node를 바꾸어주고, 그리고 prev에 current를 넣어주고 current에 next_node를 넣어주는 방식으로 문제를 풀었다.

코드는 다음과 같다.

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