Reverse Linked List

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a linked list, return a reverse list in $O(1)$

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Linked List
• Two Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each item in the list once
• Space: $O(1)$ → Reason: Not storing a copy of the list

Code

# 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]:
        prev, cur = None, head

        while cur:
            next = cur.next
            cur.next = prev
            prev, cur = cur, next

        return prev

Common Mistakes / Things I Got Stuck On

• Tried to use a Dummy Node