Fastest Wins! - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Linked Lists, Sorting, Insertion Sort

1: U-nderstand

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

  • Q: What does the problem ask for?
    • A: The problem asks to sort a linked list using the insertion sort technique.
  • Q: How should the linked list be sorted?
    • A: The list should be sorted in ascending order, with each element being placed in its correct position one by one.
HAPPY CASE
Input: head1 = Node(4, Node(2, Node(1, Node(3))))
Output: 1 -> 2 -> 3 -> 4
Explanation: The linked list is sorted in ascending order using insertion sort.

HAPPY CASE
Input: head2 = Node(-1, Node(5, Node(3, Node(4, Node(0)))))
Output: -1 -> 0 -> 3 -> 4 -> 5
Explanation: The linked list is sorted in ascending order using insertion sort.

EDGE CASE
Input: head = None
Output: None
Explanation: An empty list remains empty.

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 Sorting via Insertion Sort, we want to consider the following approaches:

  • Insertion Sort: As we traverse the list, each node is inserted into its correct position in the sorted part of the list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use a temporary head node to simplify the insertion process. As we traverse the original list, each node will be removed from the unsorted part and inserted into its correct position in the sorted part.

1) Initialize a temporary `head` node to help with insertion.
2) Traverse the original list:
    a) For each `node`, find its correct position in the sorted part.
    b) Insert the `node` into the sorted part.
3) Return the `head` of the sorted list.

⚠️ Common Mistakes

  • Forgetting to handle cases where the list is empty or contains only one node.
  • Incorrectly linking nodes, leading to loss of nodes or incorrect order.

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 sort the linked list using insertion sort
def sort_list(head):
    if not head:
        return None

    sorted_head = Node(0)  # Temporary head
    current = head  # Current node to be inserted

    while current:
        # At each iteration, current is the node to be inserted into the sorted part
        prev_node = sorted_head  # Start from the temp head node every time
        next_node = current.next  # Store the next node before modifying current.next

        # Find the correct spot in the sorted part
        while prev_node.next and prev_node.next.value < current.value:
            prev_node = prev_node.next

        # Insert current into the sorted part
        current.next = prev_node.next
        prev_node.next = current

        # Move to the next node in the original list
        current = next_node

    return sorted_head.next

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 head1 and head2 linked lists to verify that the function correctly sorts the list using insertion sort.

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^2) because, for each node, the algorithm may need to traverse the sorted part of the list to find the correct position.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.