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->4, 1->3->4
Output: 1->1->2->3->4->4
Input: 4->7->10 -4->3->4->5
Output: -4->3->4->4->5->7->10
EDGE CASE
Input: [ ], [ ]
Output: [ ]
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 problems, we want to consider the following approaches:
⚠️ Common Mistakes
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Iterate through both lists and store their values in an array. Sort the array. Rebuild the linked list with the values in the array.
1) Initialize an empty array that will store our lists' values
2) Iterate through both LLs and add their values to the empty array
3) Sort the array
4) Iterate through the array, building a new LL with each node having a value from the array
5) Return the head of the new LLGeneral Idea: Build a new linked list. In each iteration, compare the head of the two linked lists. Whichever head has the smaller value gets added to the new linked list we're building. Continue iterating until one list is null, and then add the rest of the other list to our newly built list.
1) Iterate over the LLs (while head1 or head2) where head1 and head2 are pointers to the heads of the input LLs
a) If head1.val <= head2.val, create and append a node with a value of head1.val to the return list.
Move head1 forward one node.
b) Otherwise, create and append a node with value of head2.val to the return list
Move head2 forward one node.
2) Figure out if either list still hasn't been fully traversed.
If it hasn't, finish traversing and adding its values to the return list
3) Return head of new LLGeneral Idea: Similar to the previous approach, but instead of building a new linked list we change the next pointers based on which value is smaller. We start with a dummy head. The dummy head's next will be whichever is the smaller head of the two linked lists. Iterate through this step until one of the list's head next is null. At which point we point it to the rest of the other list.
1) Instantiate a new node with a value of 0.
This will be our dummy node, the node to the left of the head of our return list.
Store a reference to this node so that we can return the list at the end.
2) Create a pointer, tail, that always points to the end of our LL. Initialize it to point to the dummy node.
3) Iterate over the LLs (while head1 or head2) where head1 and head2 are pointers to the heads of the input LLs
a) If head1.val <= head2.val, append head1 to the list by pointing tail's next pointer to head1.
Move head1 forward one node.
b) Otherwise, append head2 to the list by pointing tail's next pointer to head2.
Move head2 forward one node
4) Move tail forward one node
5) Figure out if either list still hasn't been fully traversed.
If it hasn't, point tail's next to the head of the list that hasn't been fully traversed.
6) Return dummy.nextImplement the code to solve the algorithm.
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# Instantiate a new node with a value of 0 + Create a pointer, tail, that always points to the end of our LL. Initialize it to point to the dummy node.
dummyNode = tail = ListNode()
# Iterate over the LLs (while head1 or head2) where head1 and head2 are pointers to the heads of the input LLs
while list1 and list2:
# If head1.val <= head2.val, append head1 to the list by pointing tail's next pointer to head1.
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
# Otherwise, append head2 to the list by pointing tail's next pointer to head2
tail.next = list2
list2 = list2.next
# Move tail forward one node
tail = tail.next
# Figure out if either list still hasn't been fully traversed. + If it hasn't, point tail's next to the head of the list that hasn't been fully traversed.
if list1:
tail.next = list1
else:
tail.next = list2
# Return dummy.next
return dummyNode.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 1. M represents the number of nodes in the linked list 2.
O(N + M) because we may need to traverse all numbers in both linked listO(1) because only need to store the dummyNode as our head pointer and tail as our tail pointer.