TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
kth
node from the beginning and the kth
node from the end of a linked list.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.
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:
kth
node from the beginning and the kth
node from the end.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
k
is out of bounds (though it is assumed 1 <= k < n
in this problem).kth
node from the end.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
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
shelf
linked list with multiple books to verify that the function correctly swaps the kth
nodes.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the linked list.
O(N)
because we traverse the entire linked list twice.O(1)
because the algorithm uses a constant amount of extra space for pointers.