Reverse Linked List
Given the head of a singly linked list, reverse the list and return its head.
Implement a function reverseList that takes the head of the linked list as input and returns the new head of the reversed list.
Refer to the ListNode class/struct and do not comment it out.
Example
Input: 1 -> 2 -> 3 -> 4 Output: 4 -> 3 -> 2 -> 1
Can you come up with a solution with a time complexity of O(n)?
Can you come up with a solution with a space complexity of O(1)?
Our solution reverses the linked list by iterating through it while maintaining pointers to keep track of the previous node and the current node. For each node, it saves the next node, then reverses the link by pointing the current node's next to the previous node. It then moves the prev pointer to the current node and advances the current pointer to the saved next node. This process continues until the end of the list is reached. At the end, the prev pointer points to the new head of the reversed list, which is returned.
The solution uses two pointers, prev and current, to achieve this reversal. This approach ensures that each node is processed exactly once, making it both efficient and straightforward.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode) -> ListNode:
prev = None
current = head
while current:
next_node = current.next # Save the next node
current.next = prev # Reverse the link
prev = current # Move prev to this node
current = next_node # Move to the next node
return prev # New head of the reversed listTime Complexity: The solution has a time complexity of O(n), where n is the number of nodes in the linked list. This is because we iterate through the list once, performing constant-time operations (pointer adjustments) for each node.
Space Complexity: The solution uses O(1) space, as it only uses a fixed amount of extra space (three pointers: prev, current, and nextNode). No additional data structures are used, making it very space-efficient.
Check out our lesson on the two pointer approach to learn more about what it is and how to use it!
Was this for an entry level engineer role?