206. Reverse Linked List#
Difficulty: Easy
Link to Problem: To see the Reverse Linked List problem on LeetCode, click here!
Given the head
of a singly linked list, reverse the list, and return the reversed list.
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?
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Function to reverse a linked list iteratively
def reverseListIterative(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# Function to reverse a linked list recursively
def reverseListRecursive(head):
if not head or not head.next:
return head
new_head = reverseListRecursive(head.next)
head.next.next = head
head.next = None
return new_head
Explanation:#
reverseListIterative(head)
: This function reverses a linked list iteratively using a loop. Here’s a step-by-step explanation:It takes the
head
of the input linked list as a parameter.It initializes two pointers,
prev
andcurrent
, initially set toNone
and thehead
of the list, respectively.It enters a
while
loop that continues untilcurrent
reaches the end of the list (i.e., becomesNone
).Inside the loop:
It stores the
next_node
which is the next node aftercurrent
.It updates the
next
pointer ofcurrent
to point to theprev
node. This effectively reverses the link direction.It moves
prev
tocurrent
andcurrent
tonext_node
, advancing the pointers one step further in the list.
Once the loop completes,
prev
will be pointing to the new head of the reversed list (which was the last node of the original list), so it returnsprev
.
reverseListRecursive(head)
: This function reverses a linked list recursively. Here’s how it works:It takes the
head
of the input linked list as a parameter.The base case is checked: if
head
isNone
orhead.next
isNone
, meaning the list is empty or has only one node, it returnshead
as there’s no need to reverse a list with zero or one element.In the recursive case:
It calls itself with
head.next
, effectively moving down the list until it reaches the end.Once it reaches the end, it starts reversing the links:
head.next.next
is set tohead
, reversing the link betweenhead
and the next node.head.next
is set toNone
to avoid cycles.
Finally, it returns the new head of the reversed list, which will be the last node of the original list.
In summary, reverseListIterative
reverses the linked list by iterating through it and changing the next pointers, while reverseListRecursive
reverses the linked list by recursively reaching the end and then reversing the links on the way back up the recursion stack. Both functions achieve the same result: reversing the linked list.
# Helper function to create a linked list from a list of values
def createLinkedList(values):
if not values:
return None
head = ListNode(values[0])
current = head
for val in values[1:]:
current.next = ListNode(val)
current = current.next
return head
# Helper function to convert a linked list to a list for testing
def linkedListToList(head):
result = []
current = head
while current:
result.append(current.val)
current = current.next
return result
Let’s explain the two helper functions used in the provided code:
createLinkedList(values)
:Purpose: This function is used to create a linked list from a list of values. It takes a list of values as input and returns the head of the linked list.
How it works:
It first checks if the input list
values
is empty. If it’s empty, it returnsNone
to indicate an empty linked list.If
values
is not empty, it initializes ahead
node with the value of the first element invalues
.It then iterates through the remaining values in
values
, creating new nodes for each value and linking them together to form a linked list.Finally, it returns the
head
node of the newly created linked list.
linkedListToList(head)
:Purpose: This function is used to convert a linked list back into a Python list for testing and output purposes.
How it works:
It takes the
head
of the linked list as input.It initializes an empty list called
result
.It then iterates through the linked list, starting from
head
, and appends each node’sval
(value) to theresult
list.This process continues until the end of the linked list is reached.
Finally, it returns the
result
list, which contains the values from the linked list in the same order.
These helper functions are used to simplify the process of creating linked lists from lists of values and converting linked lists back into lists, making it easier to work with linked lists in the provided examples and test cases.
Test cases#
# Example 1: Iterative
head1 = [1,2,3,4,5]
head1 = createLinkedList(head1)
reversed_head1 = reverseListIterative(head1)
print(linkedListToList(reversed_head1))
[5, 4, 3, 2, 1]
# Example 2: Recursive
head2 = [1,2]
head2 = createLinkedList(head2)
reversed_head2 = reverseListRecursive(head2)
print(linkedListToList(reversed_head2))
[2, 1]
# Example 3: Empty list
head3 = []
head3 = createLinkedList(head3)
reversed_head3 = reverseListIterative(head3)
print(linkedListToList(reversed_head3))
[]
Let’s analyze the time and space complexity of the two functions:
reverseListIterative(head)
:Time Complexity:
The iterative function visits each node in the linked list exactly once in a single pass, where “
” is the number of nodes in the list. Therefore, the time complexity is linear in the number of nodes.
Space Complexity:
This function uses a constant amount of extra space for the
prev
,current
, andnext_node
pointers. Regardless of the size of the input list, the amount of additional memory used remains the same, so the space complexity is constant.
reverseListRecursive(head)
:Time Complexity:
The recursive function also visits each node in the linked list exactly once. It recursively traverses the list from the head to the tail, reversing the links on the way back. Therefore, like the iterative approach, the time complexity is
, where “ ” is the number of nodes.
Space Complexity:
The recursive function uses space on the call stack for each recursive call. In the worst case, when the list has “
” nodes, it will create “ ” recursive function calls on the stack, resulting in a space complexity of . This is because each function call stores information about its state, including thehead
pointer, until it reaches the base case and starts returning.
In summary:
The time complexity of both functions is
because they both visit each node once.The space complexity of
reverseListIterative
is because it uses a constant amount of extra space.The space complexity of
reverseListRecursive
is due to the recursive function calls and the associated call stack space.
Both functions are efficient in terms of time complexity, but reverseListIterative
is more memory-efficient because it uses a constant amount of additional space, while reverseListRecursive
uses space on the call stack proportional to the number of nodes in the list.
Challenging Exercises:#
K-Group Reverse: Modify the reverseListIterative function to reverse the linked list in groups of
elements. For example, if the input linked list is [1, 2, 3, 4, 5, 6], and is 3, the output should be [3, 2, 1, 6, 5, 4].Rotate Linked List: Write a function to rotate a linked list to the right by
places. For example, if the input is [1, 2, 3, 4, 5] and is 2, the output should be [4, 5, 1, 2, 3].