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?
Be sure that you clarify the input and output parameters of the problem:
Run through a set of example cases:
HAPPY CASE
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Input: head = []
Output: []
EDGE CASE
Input: head = [1]
Output: [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.
Plan the solution with appropriate visualizations and pseudocode.
1) Establish a temp head that points to the first node
2) Keep a pointer to the temp head
3) Iterate through the list while the pointer has TWO valid nodes ahead
4) Swap the two nodes ahead of the pointer
5) Move the pointer to the second post-swap node
6) Continue to iterate until end of list
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# initialize one temp node and mark it as prev node
prev = tempHead = ListNode(0, next = head)
# check the next node and next next node exist
while prev.next and prev.next.next:
# get the next node and next next node exist
first = prev.next
second = prev.next.next
# set first.next to second.next, point to next node pair
first.next = second.next
# set second.next to first, perform the swap
second.next = first
# set prev.next to second, point to current node pair
prev.next = second
# set prev to first, set prev to node previous to next node pair
prev = first
return tempHead.next
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode d = new ListNode(-1);
d.next = head;
// initialize one temp node and mark it as prev node
ListNode prev = d;
while(head != null && head.next!=null){
// get the current node and next node
ListNode a = head;
ListNode b = head.next;
// now previous node's next node becomes b
prev.next = b;
// connect b nodes next to a nodes next to preserve chaining
a.next = b.next;
// to make a node comes after b,
b.next = a;
// now a node becomes previous
prev = a;
// iterate to next pair of nodes
head= a.next;
}
return d.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.