A New Perspective - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Linked Lists, Rotation, Circular Lists

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 rotate a linked list to the right by k places.
  • What should be returned?
    • The function should return the head of the rotated linked list.
HAPPY CASE
Input: evidence_list1 = Node(1, Node(2, Node(3, Node(4, Node(5)))))
       k = 2
Output: 4 -> 5 -> 1 -> 2 -> 3
Explanation: The list is rotated to the right by 2 places.

HAPPY CASE
Input: evidence_list2 = Node(0, Node(1, Node(2)))
       k = 4
Output: 2 -> 0 -> 1
Explanation: The list is rotated to the right by 4 places. Since 4 % 3 = 1, it's equivalent to rotating by 1 place.

EDGE CASE
Input: evidence_list = Node(1)
       k = 10
Output: 1
Explanation: A single-node list remains unchanged regardless of the value of `k`.

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 Rotation, we want to consider the following approaches:

  • Circular List: Treat the list as circular by connecting the tail to the head and then breaking the circle at the correct point.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will first determine the length of the linked list. Then, we'll normalize k by taking the modulus with the length of the list. Next, we'll identify the new head and tail of the rotated list by moving the appropriate number of nodes from the head. Finally, we'll break the circular connection to return the rotated list.

1) If the list is empty, has only one node, or `k` is 0, return the list as is.
2) Calculate the length of the list by traversing it and keeping track of the tail.
3) Normalize `k` by taking `k % length`.
4) If `k` is 0 after normalization, return the list as is.
5) Find the new tail by moving `length - k - 1` steps from the head.
6) Set the new head as the node after the new tail.
7) Make the list circular by connecting the old tail to the head.
8) Break the circular connection by setting the new tail's next pointer to None.
9) Return the new head.

⚠️ Common Mistakes

  • Forgetting to handle cases where k is larger than the length of the list.
  • Incorrectly managing pointers, leading to cycles or loss of nodes.

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 rotate the linked list to the right by k places
def rotate_right(head, k):
    if not head or not head.next or k == 0:
        return head
    
    # Step 1: Calculate the length of the list
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    
    # Step 2: Normalize k
    k = k % length
    if k == 0:
        return head  # No change needed
    
    # Step 3: Find the new head
    new_tail_position = length - k - 1
    new_tail = head
    for _ in range(new_tail_position):
        new_tail = new_tail.next
    
    new_head = new_tail.next
    
    # Step 4: Rearrange pointers
    tail.next = head  # Connect the old tail to the head to make it circular
    new_tail.next = None  # Break the circle
    
    # Step 5: Return the new head
    return new_head

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 evidence_list1 and evidence_list2 linked lists with different values of k to verify that the function correctly rotates 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 the algorithm uses a constant amount of extra space for pointers.