15. Reverse Linked List

🎯 leetcode - 206. Reverse Linked List

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 15번 문제
- 역순 연결리스트 구현하기

📌 날짜

2020.01.25

📌 시도 횟수

2 try

💡 Code

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        q: Deque = deque()
        while head:
            q.appendleft(head.val)
            head = head.next

        dummy = list_node = ListNode(0)
        for num in q:
            list_node.next = ListNode(num)
            list_node = list_node.next
        return dummy.next

💡 문제 해결 방법

- 연결 리스트를 deque로 옮긴 후, 다시 연결리스트로 변환했다.
- 역순이므로 deque의 appendleft()를 이용했다.
- 따라서 각 노드 값을 순회할때마다 deque의 맨 앞에 값이 쌓이게 된다.
- 이렇게 저장된 값을 차례대로 연결 리스트의 노드에 넣어 리턴하면 된다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 다른 자료형으로 옮기지 않고 연결리스트로만 구현하려고 했는데 잘 안 풀렸다.
- 그래서 결국 deque로 옮겨서 풀었다.😥
- 다음에 다시 풀 때는 연결리스트만을 이용하여 풀어보자.

---

😉 다른 풀이

📌 하나. 반복 구조로 뒤집기

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev

💡 문제 해결 방법

• 1. 이해가 잘 안되면 이 gif를 참고
     
• 2. 코드 뜯어서 그림으로 이해하기
     

+ 참고로...

• 이렇게 한 줄로 처리할 수도 있다.
• 이때 while문 안의 다중할당 순서는 매우매우 중요하다!
• 이렇게 다중할당으로 처리된 부분은 조금 헷갈릴 수 있다. 따라서 위의 그림을 보고 각각의 prev, node가 어떻게 이동하는 지 순서를 머릿속으로 그려보면서 코드를 이해하도록 하자~

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        while node:
            node.next, prev, node  = prev, node, node.next
        return prev

💡 새롭게 알게 된 점

- 반복문 방법을 떠올리면서 연결 리스트 문제를 풀려고 하니 잘 안됐던 것 같다.
- 순차적으로만 접근이 가능한 연결리스트의 특성을 잘 고려해서 문제를 풀어야겠다.

---

📌 둘. 재귀로 뒤집기

class Solution:
    def reverseList(self, head: ListNode, prev=None) -> ListNode:
        if not head:
            return prev
        next = head.next
        head.next = prev
        return self.reverseList(next, head)

💡 새롭게 알게 된 점

- 위의 반복 구조로 푸는 방법과 거의 비슷하다!
- 단, 재귀에서는 head와 prev를 reverseList(next, head)를 이용하여 오른쪽으로 이동시킨다.
- head, prev는 재귀 구조를 반복할 때마다 오른쪽으로 이동한다.
- 그리고 최종적으로는 prev를 리턴하는데 그 때의 linked list는 아래 그림과 같다.