[리트코드] 206. 역순 연결 리스트 (Python)

Reverse Linked List - LeetCode

문제

연결 리스트가 주어지면 연순으로 출력하기

 

과정

1. 처음 값과 이 전값을 넣어줄 변수를 생성한다.
2. 노드가 가리키는게 없을 때까지 값의 위치를 계속 바꾸어준다.

 

입력

[1,2,3,4,5]

출력

[5,4,3,2,1]

 

풀이

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

 

한 줄씩 코드 해석해보기

node, prev = head, None

• node 변수에 기존 값 head를 넣어주고 prev 변수에는 None을 넣은채로 생성해준다.

while node:
    next, node.next = node.next, prev
    prev, node = node, next

return prev

• 노드에 값이 없을 때까지 반복한다.
• next 변수에는 현재 노드의 다음값 부터 넣고 노드의 다음값에는 prev값을 넣어준다.
• 그 다음 prev 변수에 노드(head)를 넣고 노드에 next를 넣어준다.
• 예를들면, 1 -> 2 -> 3 -> 4 -> 5 라는 연결 리스트가 있다. 처음에 next에는 node의 다음값 부터 들어가기 때문에
  노드에는 1만 남고 next에 2 -> 3 -> 4 -> 5 가 들어가게 된다. node.next에는 처음 prev 값인 None이 들어가게 된다.
• 그 다음, prev 변수에 node(head)인 1이 들어가게되고 node에는 next에 저장했던 2 -> 3 -> 4 -> 5가 들어가게된다.
• 즉, prev = 1 , node = 2 -> 3 -> 4 -> 5 가 된다.
• 이것을 반복하면 이 다음에는 node에는 2만 남고 나머지를 next에 넣어준다. 그다음 node.next에 prev를 넣어주니까
• next = 3 -> 4 -> 5 node = 2 -> 1 이 된다. 그 후 과정을 반복하면
• prev = 2 -> 1 node = 3 -> 4 -> 5 가 된다.
• 이런 식으로 계속 값을 바꿔주면서 저장하게 된다.

 

재귀를 사용한 풀이

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node, prev=None): # 재귀 함수를 만들어 준다.
            if not node: # 만약 node에 값이 없다면
                return prev # prev 를 반환한다.
            next, node.next = node.next, prev # next라는 변수를 하나 만들어서 node의 next부터를 저장시키고 
            return reverse(next, node) 	      # node의 next를 prev로 지정 해준다. (node가 None이 될때까지)          
        return reverse(head) # 재귀