-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathreverse-linked-list.py
105 lines (93 loc) · 3.18 KB
/
reverse-linked-list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# 206. Reverse Linked List
# 🟢 Easy
#
# https://leetcode.com/problems/reverse-linked-list/
#
# Tags: Linked List - Recursion
import timeit
from typing import Optional
from utils.linked_list import LinkedList
from utils.list_node import ListNode
# Iterate over all the list nodes, for each, create a temporary pointer
# to it, then make the right node point to the left one and the left to
# the next one.
#
# Time complexity: O(n) - We visit each node once.
# Space complexity: O(1) - We use constant memory.
#
# Runtime: 39 ms, faster than 92.11%
# Memory Usage: 15.4 MB, less than 55.68%
class Iterative:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
current, next = head, head.next
while next:
# Get a reference to the current node to point its next to
# later, then shift current and next pointers forward.
prev, current, next = current, next, next.next
# Reverse the pointer from current.
current.next = prev
head.next = None
# Return the head of the reversed list.
return current
# A shorter version, probably easier to remember and use as a standard
# way to reverse a linked list.
#
# Time complexity: O(n) - We visit each node once.
# Space complexity: O(1) - We use constant memory.
#
# Runtime: 45 ms, faster than 81.14%
# Memory Usage: 15.4 MB, less than 94.40%
class Iterative2:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
current, prev = head, None
while current:
current.next, current, prev = prev, current.next, current
return prev
# Recursively call the function with each node and its previous one.
#
# Time complexity: O(n) - We visit each node once.
# Space complexity: O(n) - The call stack will have one call for each
# node in the input list.
#
# Runtime: 96 ms, faster than 5.40%
# Memory Usage: 20.5 MB, less than 8.12%
class Recursive:
def reverseList(
self, head: Optional[ListNode], prev: Optional[ListNode] = None
) -> Optional[ListNode]:
if not head:
return prev
curr, head.next = head.next, prev
return self.reverseList(curr, head)
def test():
executors = [
Iterative,
Iterative2,
Recursive,
]
tests = [
[[], []],
[[1, 2], [2, 1]],
[[1, 2, 3, 4, 5], [5, 4, 3, 2, 1]],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
head = LinkedList.fromList(t[0]).getHead()
result = sol.reverseList(head)
result = LinkedList(result).toList()
exp = t[1]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()