[Top Interview Questions] 206. Reverse Linked List

정답)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newTail = None
        newHead = None

        while head:
            newHead = ListNode(head.val)
            newHead.next = newTail

            head = head.next
            newTail = newHead
        
        return newHead

문제)

문제출처

 

Singly linked list의 head가 주어졌을 때, 이 리스트가 거꾸로 변환된 리스트를 리턴하시오.

 

예시 1)

예시 2)

예시 3)

head = []

output = []

 

제한)

리스트에는 0~5000개의 노드가 존재합니다.

-5000 <= node.val <= 5000

 

도전)

변환하는 방법에는 순차적으로 변환시키는 방법과 recursive하게 변환시키는 방법 2가지가 존재합니다. 

풀이)

총 3개의 노드가 있습니다.

1) head: 리스트를 차례차례 선형 하면서 리스트에 존재하는 숫자들을 알려줄 노드

2) newTail: 이때까지 변환시킨 노드들을 기억하고 있어 줄 노드

3) newHead: 리버스 된 리스트의 맨 앞에 새롭게 붙을 노드 

 

이 3개의 노드가 각각 어떤 역할을 갖고 움직이는지 생각하시면서 풀이를 읽어주세요.

 

newHead와 newTail들은 None으로 시작합니다.

 

본래의 리스트를 선형 하는 동안,

newHead는 본래의 리스트의 새롭게 발견되는 노드의 val을 가질 것입니다.

새로운 숫자로 업데이트된 newHead를 newTail의 맨 앞에 붙여줍니다. 이렇게 할 경우에 새로운 숫자의 노드가 기존의 노드 앞에 붙게 됨으로써 리스트가 리버스 됩니다.

 

원리

이런 식으로 본래의 리스트를 전부 선형 하면 리버스 된 리스트를 리턴합니다.

 

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newTail, newHead 노드

        원래 리스트를 선형하는 동안
            newHead는 리스트의 새롭게 발견되는 노드
            newHead를 newTail의 맨 앞에 붙여줍니다

            head를 다음 노드로 업데이트
            newTail을 newHead로 업데이트해 다음 루프 때 새로운 노드를 붙일 수 있게 해줍니다.
        
        newHead를 리턴

초기세팅)

문제에서 본 리스트의 개수가 0개일 수도 있다고 했기 때문에 일단은 newTail과 newHead를 Null로 저장해 줍니다.

이럴 경우 다음의 while 루프 없이 바로 Null을 리턴합니다.

 

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newTail = None
        newHead = None

while문 1)

head 노드를 이용하여 리스트를 선형 해줍니다.

head가 Null이 아니라는 뜻은 리스트에 노드가 존재한다는 뜻입니다.

그래서 head가 Null이 아닌 실제 노드일 때 밑 문장들을 실행합니다.

 

newHead에 현재 head노드의 val값을 가진 노드를 저장해 줍니다.

 

그리고 위에서 말했듯이 newTail의 맨 앞에 newHead를 붙여줍니다.

거꾸로 생각하면 newHead의 next가 newTail입니다.

 

위 문장들의 과정

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newTail = None
        newHead = None

        while head:
            newHead = ListNode(head.val)
            newHead.next = newTail

while문 2)

위에서 새로운 노드를 붙여줬다면 이제 노드들의 위치를 업데이트해 줘야 됩니다.

 

리스트의 첫 번째 노드의 값을 찾아서 저장했다면 이제 두 번째 노드의 값을 알아야겠죠?

head를 head.next의 자리로 옮겨줍시다.

 

그리고 newTail 또한 다음 자리인 newHead로 옮겨줍니다.

이렇게 자리를 움직여 줘야지 다음 루프 때도 새로운 노드를 맨 앞에 붙여줄 수 있습니다.

 

head/newTail의 업데이트

그렇게 리스트의 모든 노드들을 선형 했다면 newHead를 리턴해 리버스된 리스트를 리턴합니다. 

 

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newTail = None
        newHead = None

        while head:
            newHead = ListNode(head.val)
            newHead.next = newTail

            head = head.next
            newTail = newHead
        
        return newHead

디버깅)

head = [1, 2, 3]

 

newTail = None

newHead = None

 

(while 1)

newHead = 1

1    =>    1 - None

head = 2

newTail = 1

 

(while 2)

newHead = 2

2    =>    2 - 1 - None

head = 3

newTail = 2

 

(while 3)

newHead = 3

3    =>    3 - 2 - 1 - None

head = None

newTail = 3

 

return newHead

 

 

이번 문제는 딕셔너리나 리스트 같은 따로 저장공간을 만들어서 풀었다면 쉬웠겠지만 이런 식으로 별도의 노드들을 이용해 풀어봤습니다. 노드와 linked list를 잘 아신다면 제 풀이가 쉬웠을 것 같은데 잘 모르시는 분들이 보셨다가 많이 헷갈리셨을까 봐 걱정이네요... 그래도 최대한 이해하시기 쉽도록 설명해 봤습니다. 일주일간 포스팅은 없을 예정입니다!

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)