Reverse Linked List - Solution
Solutions and explanations
# 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: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head
Complexity Analysis
Here, n is the numbers of nodes in the input linked list.
- Time Complexity:
O(n)- as we visit each node exactly once to reverse its connections. - Space Complexity:
O(n)- due to the space used by recursion stack.
# 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: Optional[ListNode]) -> Optional[ListNode]:
cur, prev = head, None
while cur:
nxt = cur.next
cur.next = prev
cur, prev = nxt, cur
return prev
Complexity Analysis
Here, n is the numbers of nodes in the input linked list.
- Time Complexity:
O(n)- as we visit each node exactly once to reverse its connections. - Space Complexity:
O(1)