Reverse a Linked List (Medium)
Good afternoon! Here's our prompt for today.
You may see this problem at Oracle, Ebay, Splunk, Yelp, Visa, Sap, Uipath, Jfrog, Lucid Software, Cockroach Labs, C3 Ai, and Bosch Global.
You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows:
SNIPPET
17 -> 2 -> 21 -> 6 -> 42 -> 10Write an algorithm for a method reverseList that takes in a head node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length.
You may use the example linked list for testing purposes. Your method will be called as such:
1class Node:
2 def __init__(self, val):
3 self.val = val
4 self.next = None
5
6l1 = Node(1)
7l1.next = Node(2)
8reverse_list(l1)Constraints
- Length of the given LinkedList <=
100000 - The nodes will always contain integer values between
-1000000000and1000000000 - Expected time complexity :
O(n) - Expected space complexity :
O(1)
xxxxxxxxxx53
def reverse_list(head): # fill in this method return head# Node definitionclass Node: def __init__(self, val): self.val = val self.next = Nonedef create_nodes(head, nodes): for val in nodes: new_node = Node(val) head.next = new_node head = new_nodelist1 = Node(3)nodes1 = [4, 5, 6, 7, 8, 9, 10]create_nodes(list1, nodes1)list2 = Node(1)nodes2 = [2, 3, 4, 5, 6, 7, 8]create_nodes(list2, nodes2)OUTPUT
Results will appear here.