How to delete repeating elements in a sorted list in LeetCode
LeetCode how to delete the repeated elements in the sorted list, I believe that many inexperienced people do not know what to do, so this paper summarizes the causes of the problem and solutions, through this article I hope you can solve this problem.
Topic description:
Given a sorted linked list, delete all duplicate elements so that each element appears only once.
Example 1:
Enter: 1-> 1-> 2
Output: 1-> 2
Example 2:
Enter: 1-> 1-> 2-> 3-> 3
Output: 1-> 2-> 3
Analysis of ideas:
This is a simple question that only tests your ability to manipulate the node pointers of the list. Because the list entered is sorted, we can determine whether it is a duplicate node by comparing the value of the node with the node that follows it. If it is repeated, we change the next pointer of the current node so that it skips the next node and points directly to the node after the next node.
Complexity analysis
Time complexity: O (n), because each node in the list is checked once to see if it is duplicated, so the total elapsed time is O (n), where n is the number of nodes in the list.
Space complexity: O (1), no extra space is used.
Python implements # 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: ListNode)-> ListNode:
# Fast and slow pointer
If not head:
Return None
Fast, slow = head, head
While fast:
If fast.val! = slow.val:
Slow.next = fast
Slow = slow.next
Fast = fast.next
Slow.next = None
Return head
Java implementation: public ListNode deleteDuplicates (ListNode head) {
ListNode current = head
While (current! = null & & current.next! = null) {
If (current.next.val = = current.val) {
Current.next = current.next.next
} else {
Current = current.next
}
}
Return head
}
Another version of the implementation:
Class Solution {
Public ListNode deleteDuplicates (ListNode head) {
If (head==null) {
Return head
}
ListNode dummhead=new ListNode (0)
Dummhead.next=head
ListNode cur=head
ListNode last=head.next
While (lastworthy null) {
If (cur.val==last.val) {
ListNode tmp=null
Tmp=last.next
Cur.next=tmp
Last=tmp
} else {
Cur=last
Last=last.next
}
}
Return dummhead.next
}
}
After reading the above, have you mastered the method of how to delete the repeating elements in the sorted list in LeetCode? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!
