Links
Go to my solution
Go to the question on LeetCode
My Thoughts
What Went Well
I knew how to traverse a linked list and use its methods. I read the constraints and all the test cases before coding.
What Went Wrong
It has been a while since I’ve reviewed linked lists, but I decided to start coding immediately. Unfortunately, the initial solution I came up with was unsuccessful, and I had to start from scratch despite having already invested 12 minutes into solving the problem.
What I Learned
I refreshed my memory on linked list traversal but realized how difficult it is if you haven’t seen it in a long time.
How I Can Improve
I’ve realized the importance of writing things out on paper rather than trying to push out a solution with no direction.
Comments
After solving the problem, the submission for this question from July last year was quite shocking. Be prepared for the craziest solution you’ve ever seen, previous solution.
Data Structure Description
Linked List - It is explained here much better than I could summarize.
Visual Examples
A Linked List being reversed, click to view
Solution Statistics
Time Spent Coding
18 minutes
Time Complexity
O(n) - We must iterate through all the elements in the list, resulting in the O(n) time complexity.
Space Complexity
O(1) - Only three new variables are created. The number of variables declared does not depend on the number of items in the list, resulting in the O(1) space complexity.
Runtime Beats
77.47% of other submissions
Memory Beats
89.12% of other sumbissions
Solution
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# If the LinkedList has 0 or 1 element, there is nothing to reverse
if head == None or head.next == None:
return head
prev = head
cur = head.next
# To avoid an infinite loop, we must make the head point to None
head.next = None
while cur.next != None:
next_cur = cur.next
cur.next = prev
prev = cur
cur = next_cur
# Include or else you will omit the last element
cur.next = prev
return cur
Previous Solution
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
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
n = ListNode()
begin = n
save = head
count = 0
if head is None:
return None
else:
while head != None:
count += 1
head = head.next
for i in range(count - 1,-1,-1):
head = save
for j in range(i):
head = head.next
n.val = head.val
if i != 0:
n.next = ListNode()
n = n.next
else:
n.next = None
return begin