Turn Back Time - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Reversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What does the problem ask for?
    • The problem asks to reverse the order of a singly linked list and return the head of the reversed list.
  • What are potential edge cases?
    • The list could be empty.
    • The list could contain only one node, in which case the reversal would simply return the same node.
HAPPY CASE
Input: events = Node("Potion Brewing", Node("Spell Casting", Node("Wand Making", Node("Dragon Taming", Node("Broomstick Flying")))))
Output: "Broomstick Flying" -> "Dragon Taming" -> "Wand Making" -> "Spell Casting" -> "Potion Brewing"
Explanation: The linked list is reversed correctly.

EDGE CASE
Input: events = Node("Potion Brewing")
Output: "Potion Brewing"
Explanation: A single-node list remains the same after reversal.

EDGE CASE
Input: events = None
Output: None
Explanation: An empty list should return None.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems involving Reversal, we want to consider the following approaches:

  • Reversal via Pointer Manipulation: By reversing the pointers in the list, we can reverse the entire list efficiently.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list while reversing the pointers as we go. We will maintain a reference to the previous node so that each node points to the previous one instead of the next one.

1) Initialize two pointers: prev as None and current as the head of the list.
2) Traverse the list:
    a) Store the next node temporarily (next_node).
    b) Reverse the link by making current.next point to prev.
    c) Move prev to the current node.
    d) Move current to the next_node.
3) When the loop ends, prev will be pointing to the new head of the reversed list.
4) Return prev as the new head of the reversed list.

⚠️ Common Mistakes

  • Not properly handling the edge cases, such as an empty list or a single-node list.
  • Forgetting to update the pointers correctly, leading to broken links or infinite loops.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Function to reverse the linked list
def reverse(events):
    prev = None
    current = events

    while current:
        next_node = current.next  # Store the next node
        current.next = prev       # Reverse the link
        prev = current            # Move prev to this node
        current = next_node       # Move to the next node

    return prev  # Prev will be the new head of the reversed list

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided events linked list and verify that the function correctly reverses the list.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because each node is visited exactly once.
  • Space Complexity: O(1) because only a constant amount of extra space is used for pointers.