Shulou(Shulou.com)06/02 Report--

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!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.