Personal evaluation: after the baptism of similar problems in the middle yesterday, this problem second solution ah ha ha

🌟 (refer to LeeCode easy 🌟, medium 🌟 🌟, difficult 🌟 🌟)

In addition, algorithm questions usually examine and analyze time complexity and space complexity, which can be referred to the author’s previous article

“Data Structures & Algorithms” series: 3. Time & Space Complexity (2)

7. Common Data Structures — Linked Lists (Part 2)

Removes duplicate elements from sorted linked lists

Topic describes

83. Delete duplicate elements from sorted linked lists

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once.

Returns a linked list of results, also in ascending order.

Example 1:

Enter: head = [1,1,2]

Output: [1, 2]

Example 2:

Enter: head = [1,1,2,3,3]

Output: [1, 2, 3]

Tip:

The number of nodes in the list is in the range [0, 300] -100 <= node. val <= 100 item data ensures that the list is in ascending order

Their thinking

Compared with yesterday’s daily question, it is nothing, similar ideas, simplified operation ~

Using traversal + sentry introduction, the idea is as follows:

  • Compare current value with subsequent value, different = “continue (sorted, can determine unique)
  • Compare the current value with the subsequent value, the same = “delete the current node, continue the loop judgment
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    dummy := &ListNode{0, head} // Introduce sentry/dummy nodes to make header deletion easier
    cur := dummy.Next
    forcur.Next ! =nil {
        if cur.Val == cur.Next.Val {
            *cur = *cur.Next // Change the pointer pointer to a non-tail node
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}
Copy the code

conclusion

Sort the basis of the linked list to re-operation, should be very handy to write out, whiteboard can also ~