[Leetcode] 206. Reverse Linked List

문제 바로가기

Iterative

Time Complexity: $O(n)$
Space Complexity: $O(1)$

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        prevNode = None
        while head:
            nextNode = head.next
            head.next = prevNode
            prevNode, head = head, nextNode
            
        return prevNode

recursive

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        root_rev = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return root_rev