Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Source
# Definition for a binary Linked List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
'''Iterative approach
Time complexity : O(n)
Space complexity : O(1)
'''
previous = None
current = head
while current: # None <-- n0 (prev) // current --> n2 --> n3 --> n4
tmp = current.next # None <-- n0 (prev) // current --> n2 (tmp) --> n3 --> n4
current.next = previous # None <-- n0 (prev) <-- current // n2 (tmp) --> n3 --> n4
previous = current # None <-- n0 <-- current (prev) // n2 (tmp) --> n3 --> n4
current = tmp # None <-- n0 <-- n1 (prev) // n2 (current) --> n3 --> n4
return previous
A linked list can be reversed either iteratively or recursively. Could you implement both?
def reverse_list(head):
'''Recursive approach (a bit more subtle).
the key is to work backwards.
Assume that the rest of the list had already been reversed,
now how do I reverse the front part?
Let's assume the list is: n1 → ... → nk-1 → nk → nk+1 → ... → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.
n1 → ... → nk-1 → nk → nk+1 ← ... ← nm
We want nk+1’s next node to point to nk.
So, nk.next.next = nk;
Be very careful that n1's next must point to None.
If you forget about this, your linked list has a cycle in it.
This bug could be caught if you test your code with a linked list of size 2.
Time complexity : O(n)
Space complexity : O(n) The extra space comes from implicit stack space due to recursion.
'''
if head is None or head.next is None: # head == None just in case of empty list
return head # head.next == None is the real base case (when p = head)
p = reverse_list(head.next)
# n0 --> _ --> nm-1 --> nm (head) --> None
# n0 --> _ --> nm-1 --> nm (p = head) --> None
# n0 --> _ --> nm-1 --> nm (p) --> None
# n0 --> _ --> nm-1 <--> nm (p)
# n0 --> _ --> nm-1 <-- nm (p) (nm-1 --> None)
#we end up with the following: _ --> nk-1 --> head --> nk+1 <-- _ <-- nm (p) (nk+1 --> None)
head.next.next = head # _ --> nk-1 --> head <--> nk+1 <-- _ <-- nm (p) (nk+1 --> nk)
head.next = None # _ --> nk-1 --> head <-- nk+1 <-- _ <-- nm (p) (head --> None)
return p