Python/코딩테스트
[Leetcode] 206.Reverse Linked List
좋은데이피치
2021. 6. 30. 12:38

연결된 리스트 뒤집기
206. Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Example 2:

Input: head = [1,2] Output: [2,1]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
-----------------------------------------------------------------------------------------------------------------------------------
풀이 1. 재귀 구조로 뒤집기
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)
풀이 2. 반복 구조로 뒤집기
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
728x90