LeetCode 83 Solution | KWY’s Blog

type

status

date

slug

summary

I am try to finish leetcode 83. my code is # Definition for singly-linked list. ...

❓ Prompt

I am try to finish leetcode 83. my code is # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() dummy.next = head curr1, curr2 = dummy, dummy.next while not curr1: if curr1.val == curr2.val: curr2 = curr2.next curr1.next = curr2 else: curr1 = curr1.next curr2 = curr2.next return dummy.next where should I change to get a right answer

💬 Answer

The issue with your current implementation lies in the condition for the while loop and the handling of the nodes inside it. You've written while not curr1:, which means your loop will never execute because curr1 is initialized to dummy, which is not None. This is the opposite of what you want. You should continue looping while curr2 (the second pointer, which traverses the linked list) is not None, as this will allow you to compare each node with its next node.

Here's how you can fix your code:

Here's what was changed and why:

I removed curr1 and curr2 because you only need one pointer to traverse the list in this case. I renamed curr1 to curr for clarity and removed curr2 entirely.

Changed the while loop condition to while curr and curr.next:. This allows the loop to continue as long as there's a node and a next node to compare, effectively checking all pairs of adjacent nodes.

Inside the loop, if curr.val == curr.next.val, it means the current node and the next node are duplicates. Instead of moving two pointers, we just set curr.next = curr.next.next to skip the duplicate node.

If the values are not equal, move curr to the next node in the list.

By following this fixed approach, your function should correctly remove all duplicates from the sorted linked list and return the modified list starting from the original head node.

If you are a software engineer who apply for microsoft. How do you express this ...

❓ Prompt

If you are a software engineer who apply for microsoft. How do you express this solution in conversation.

💬 Answer

If I were a software engineer explaining this solution during an interview with Microsoft, I would approach it in a structured manner to ensure clarity and thoroughness. Here's how I would express this solution:

Starting with the Problem Understanding:

"Leetcode Problem 83 asks us to remove all duplicates from a sorted linked list. The key points to note here are 'sorted list' and 'remove duplicates'. The sorted nature of the list means all duplicates are adjacent, which simplifies our approach since we only need to compare each node with its next to identify duplicates."

Explaining the Approach:

"To tackle this problem, I propose using a single-pointer traversal method. Since the input is a singly linked list, we need a mechanism to iterate through each node and compare it with its subsequent node. If two consecutive nodes contain the same value, we'll bypass the duplicate by adjusting the next pointer of the current node to point to the node after the duplicate. This effectively removes the duplicate from the list."

Detailing the Implementation:

"Let's start by creating a dummy node, which is a common technique when modifying list heads in linked list problems. This dummy node points to the head of the original list. We then proceed with a single pointer, let's call it 'current', initialized to point at the head of the list. We iterate through the list with a while loop, which continues as long as 'current' and 'current.next' both exist."

"As we iterate, if 'current' and 'current.next' have the same value, it indicates a duplicate. We handle this by setting 'current.next' to 'current.next.next', skipping over the duplicate node. If they're not equal, we simply move 'current' forward by one node. This strategy ensures that we only keep the first element of each set of duplicates."

Finalizing and Returning the Result:

"After we've traversed the entire list and removed all duplicates, we return the modified list. However, since we introduced a dummy node at the beginning, we'll return 'dummy.next' to skip the dummy and return the actual head of the modified list."

Addressing Edge Cases and Complexity:

"This solution is efficient, with a time complexity of O(n), where n is the number of nodes in the list, because we make a single pass through the list. The space complexity is O(1) since we only use a fixed amount of extra space regardless of the input size."

Conclusion:

"In summary, this solution is straightforward, efficient, and leverages the characteristics of the sorted linked list to ensure all duplicates are removed without the need for additional data structures."

This approach not only shows your problem-solving skills but also demonstrates your ability to communicate complex ideas clearly and methodically, a valuable trait in any software engineering role, especially at a company like Microsoft.

can you tell me why you use " while curr and curr.next:"

❓ Prompt

can you tell me why you use " while curr and curr.next:"

💬 Answer

Sure, I'd be happy to explain that.

In the context of this solution, the loop while curr and curr.next: serves a couple of critical purposes:

Ensuring Safety in Accessing curr.next: We use curr and curr.next in the loop condition to ensure that we do not encounter a NoneType error when accessing curr.next. This is important because:

curr: We need to make sure that the current node is not None before we attempt to access its next property. If curr is None, it means we've reached the end of the list, and there's nothing left to check or remove.

curr.next: We also need to check that curr.next is not None. This is because our duplicate removal logic requires us to look ahead to the next node (curr.next). If curr.next is None, it means the current node is the last in the list, and there cannot be any duplicates after it, so there's no need to continue the loop.

Logical Progression Through the List: This condition naturally progresses us through the list from the beginning to the end. Each iteration of the loop deals with the node pointed to by curr and its immediate successor. We check if they hold the same value (indicating a duplicate). If they do, we remove the successor by skipping it. If they don't, we simply move curr to the next node in the list.

Efficiency and Completeness: This loop allows us to check every pair of adjacent nodes in the list exactly once. Since the list is sorted, any duplicates must be adjacent. By checking each node against its next neighbor, we ensure that all duplicates are identified and removed in a single pass through the list, making the solution efficient.

By combining these conditions into the while loop's condition, we make the code robust against common linked list issues like trying to access attributes of None, and we ensure the algorithm works correctly for all valid input lists. It's a concise way to make sure that as long as there are at least two consecutive nodes to compare, the loop continues to check for and remove duplicates.