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?
HAPPY CASE Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8, k = 3 Output: 3 <-> 2 <-> 1 <-> 6 <-> 5 <-> 4 <-> 8 <-> 7 Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8, k = 2 Output: 2 <-> 1 <-> 4 <-> 3 <-> 6 <-> 5 <-> 8 <-> 7 EDGE CASE Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8, k = 10 Output: 8 <-> 7 <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1
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 Lists, some things we should consider are:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: "chunk" the original linked list into "chunks" of size k. Then, reverse only that "chunk" of linked list. For instance, given [1, 2, 3, 4, 5, 6, 7] and k=3, handle the "chunks" [1, 2, 3] and [4, 5, 6] and 
1. Create dummy node to reference new head 2. Create previous pod to point at next reversed pod 3. Create current pod to be reveresed 4. While there is a pod to be reversed repeat the following 1. Create pointer to the next pod 2. If there is a next pod disconnect it from the current pod 3. Reverse the current pod and get the head and tail 4. Set the previous pod to point to the new head 5. Set the new head to point to the previous pod 6. Set the new previous pod to the tail 7. Set the new current pod to next pod 5.Set the head to dummy.next and disconnect head from dummy 6.Return the new head node
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def reverseListByPod(head: LinkedListNode, k: int) -> LinkedListNode: if k == -1: return None # Create dummy node to reference new head dummyNode = LinkedListNode("H") # Create previous pod to point at next reversed pod prevPod = dummyNode # Create current pod to be reveresed currPod = head # While there is a pod to be reversed repeat the following while currPod: # Get the next pod nextPod = getNextPod(currPod, k) # If there is a next pod disconnect it from the current pod if nextPod: nextPod.prev.next = None nextPod.prev = None # Reverse the current pod and get the head and tail head, tail = reverseList(currPod) # Set the previous pod to point to the new head prevPod.next = head # Set the new head to point to the previous pod head.prev = prevPod # Set the new previous pod to the tail prevPod = tail # Set the new current pod to next pod currPod = nextPod # Set the head to dummy.next and disconnect head from dummy head = dummyNode.next dummyNode.next = None head.prev = None # Return the new head node return head def getNextPod(node: LinkedListNode, k: int) -> LinkedListNode: # Get the node k spaces away if k <= 0: return None while k and node: node = node.next k -= 1 return node def reverseList(head: LinkedListNode) -> (LinkedListNode, LinkedListNode): # Reverse Linked List and return the head and tail node if not head: return None dummyNode = LinkedListNode("H") dummyNode.next = head prev, curr = dummyNode, head while curr: next = curr.next curr.next = prev prev.prev = curr prev = curr curr = next head = prev # get tail node tail = dummyNode.prev # remove link from head node head.prev = None # remove link to and from dummyNode dummyNode.prev.next = None dummyNode.next = None return (head, tail) class LinkedListNode: def __init__(self, val, next=None, prev=None): self.val = val self.next = next self.prev = prev def __repr__(self): node = self vals = reverseVals= while node: vals.append(str(node.val)) prev = node node = node.next
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
N represents the number of nodes in the doubly linked list.
O(N)because we will need to access each node in the linked list.
O(1)because we only need the previous, current, and next pointers to solve this problem.