head of a singly linked list, reverse the list, and return the reversed list.
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Input: head = [1,2] Output: [2,1]
Input: head =  Output: 
- The number of nodes in the list is the range
-5000 <= Node.val <= 5000
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # time: O(n) memory O(n) if not head or not head.next: # basecase return head # recrusive action, we repeatedly call reverseList with head.next # because of how recursive actions work we will be at the last node when we # "unwind", aka we will go backwards when we execute code after node =.... # Instead of recursing the entire linked list we will recurse the remainder of the linked list # from the head # this creates a sub-problem, we now only have N - 1 nodes to deal with. # We break it down even more and say "recurse all apart from head.next" so we get N - 2 nodes to deal with # and so on. node = self.reverseList(head.next) # When the above line finishes, it returns the head of the reversed list (which is the last node in the original list). When you do `original_last_node.next` it points to None, since it's the last node in the original list. # head.next.next = head appends the original head to the end of the reversed list (the true end) # **original list** # head -> head.next -> head.next.next -> ... -> node # **node = self.reverseList(head.next)** # node -> ... -> head.next -> None # Return node # node -> ... -> head.next -> head -> None # Since we recurse down to the last node, we only have NODE_X to access so we cannt point it back to the previous node in a singly linked list # therefore we keep it pointing at None # So when we finally finish up we need to clean up the mess we made lolsies head.next.next = head head.next = None return node
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # time: O(n) memory O(1) # The idea is that we iterate through the list and set the previous node to the node 1 befire # our current node # we then set our current node to point at our previous node # so we reverse the list in place prev = None while head: curr = head head = head.next curr.next = prev prev = curr return prev