Properly Reshelve - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Two-pointer Technique, Swapping

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 swap the values of the kth node from the beginning and the kth node from the end of a linked list.
  • Q: What should be returned?
    • A: The function should return the head of the linked list after performing the swap.
HAPPY CASE
Input: 
    - shelf = Node('Book 1', Node('Book 2', Node('Book 3', Node('Book 4', Node('Book 5')))))
    - k = 2
Output: 
    - Book 1 -> Book 4 -> Book 3 -> Book 2 -> Book 5
Explanation: 
    - The 2nd book from the start and the 2nd book from the end are swapped.

EDGE CASE
Input: 
    - shelf = Node('Book 1', Node('Book 2', Node('Book 3')))
    - k = 1
Output: 
    - Book 3 -> Book 2 -> Book 1
Explanation: 
    - The 1st book from the start and the 1st book from the end are swapped.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Swapping Nodes, Two-pointer Technique, etc.

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

  • Two-pointer Technique: Use two pointers to find the kth node from the beginning and the kth node from the end.
  • Traversal: Traverse the list to calculate its length and then identify the nodes to swap.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list to find its length, then use two separate traversals to find the kth node from the beginning and the kth node from the end. Finally, we will swap the values of these two nodes.

1) Traverse the linked list to determine its length.
2) Traverse the list again to find the `kth` node from the beginning.
3) Traverse the list to find the `kth` node from the end.
4) Swap the values of the two identified nodes.
5) Return the head of the modified linked list.

⚠️ Common Mistakes

  • Forgetting to handle cases where k is out of bounds (though it is assumed 1 <= k < n in this problem).
  • Incorrectly calculating the position of the kth node from the end.

4: I-mplement

Implement the code to solve the algorithm.

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

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

def swap_books(shelf, k):
    # Step 1: Determine the length of the linked list
    current = shelf
    length = 0
    while current:
        length += 1
        current = current.next
    
    # Step 2: Find the kth node from the beginning
    kth_from_start = shelf
    for _ in range(k - 1):
        kth_from_start = kth_from_start.next
    
    # Step 3: Find the kth node from the end
    kth_from_end = shelf
    for _ in range(length - k):
        kth_from_end = kth_from_end.next
    
    # Step 4: Swap the values of the two nodes
    kth_from_start.value, kth_from_end.value = kth_from_end.value, kth_from_start.value
    
    return shelf

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 shelf linked list with multiple books to verify that the function correctly swaps the kth nodes.

6: E-valuate

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

Assume N represents the length of the linked list.

  • Time Complexity: O(N) because we traverse the entire linked list twice.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.