[알고리즘] 역순 연결 리스트
내 풀이
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
Author And Source
이 문제에 관하여([알고리즘] 역순 연결 리스트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-역순-연결-리스트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)