[알고리즘] 역순 연결 리스트

역순 연결 리스트

내 풀이

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        tmp = []
        while head != None:
            tmp.append(head.val)
            head = head.next

        return_head = tail = ListNode()
        for num in tmp[::-1]:
            tail.next = ListNode(num)
            tail = tail.next

        return return_head.next

주어진 링크드리스트를 순서대로 따라가며 리스트에 숫자들을 저장해 놓는다. 그것을 뒤집어서 거꾸로 링크드리스트를 새로 만든다.

책 풀이

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

        return reverse(head)

다음 노드 next와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다. node.next에는 이전 prev 리스트를 계속 연결해주면서 node가 None이 될 때까지 재귀 호출하면 마지막에는 백트랙킹되면서 연결 리스트가 거꾸로 연결된다. 여기에 맨 처음에 리턴된 prev는 뒤집힌 연결리스트의 첫 번째 노드가 된다.

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