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?
N
represents the number of nodes in the linked list. O(N)
time and O(1)
Space, ignoring the recursive stack.HAPPY CASE
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Input: head = [1,2,3,4,5], left = 1, right = 5
Output: [5,4,3,2,1]
EDGE CASE
Input: head = [5], left = 1, right = 1
Output: [5]
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, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will reverse everything in between the left and right index. Then we will point to the new head and tail.
1) Eliminate Edge Case, left and right is equal
2) Initialize dummy node, left previous pointer, left pointer
3) Move left previous pointer to left previous and left pointer to left
4) Reverse all nodes from left pointer until right pointer
5) Insert reversed section into linked list
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
# Eliminate Edge Case, left and right is equal
if left == right:
return head
# Initialize dummy node, left previous pointer, left pointer
leftPrevious = dummy = ListNode(0,head)
leftPointer = head
# Move left previous pointer to left previous and left pointer to left
for i in range(left-1):
leftPrevious = leftPointer
leftPointer= leftPointer.next
# Reverse all nodes from left pointer until right pointer
prev = None
curr = reversedEndPointer = leftPointer
for i in range(right-left+1):
next = curr.next
curr.next = prev
prev = curr
curr = next
# Insert reversed section into linked list
reversedStartPointer = prev
restartPointer = curr
reversedEndPointer.next = restartPointer
leftPrevious.next = reversedStartPointer
return dummy.next
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// Initialize dummy node, left previous pointer, left pointer
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// Move left previous pointer to left previous and left pointer to left
for(int i = 0; i < left - 1; i++)
prev = prev.next;
// Reverse all nodes from left pointer until right pointer
ListNode curr = prev.next;
for(int i = 0; i < right - left; i++){
ListNode forw = curr.next;
curr.next = forw.next;
forw.next = prev.next;
prev.next = forw;
}
return dummy.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.
Assume N
represents the number of nodes in the linked list.
O(N)
because we may need to traverse all the nodes in the linked list.O(1)
because we only need several pointers for memory.