This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

The title

Given the head of a sorted list, remove all duplicate elements so that each element appears only once *. Returns a sorted linked list.

Example 1

Input: head = [1,2]Copy the code

Example 2

Head = [1,1,2,3,3]Copy the code

prompt

  • The number of nodes in the linked list is in the range [0, 300]
  • -100 <= Node.val <= 100
  • The subject data ensures that the linked list is sorted in ascending order

Answer key

A traversal

Train of thought

Since a given list is sorted, repeated elements appear consecutively in the list, so we only need to traverse the list once to remove the repeated elements.

Specifically, we start with a pointer cur to the head node of the list, and then start traversing the list. If the current cur and cur.next correspond to the same element, we remove cur.next from the list; Otherwise, there are no other nodes in the linked list that correspond to cur, so you can point to cur.next.

When the list is complete, we return to the head of the list.

Note: When we traverse to the last node in the list, cur.next is empty. Without judgment, accessing the element corresponding to cur.next will cause a runtime error. So we only need to traverse the last node of the list, not the entire list.

code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode cur = head;
        while(cur.next ! =null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else{ cur = cur.next; }}returnhead; }}Copy the code

Time complexity: O(n), where n is the length of the list

Space complexity: O(1)

conclusion

Practice makes perfect, shortage in one; Success depends on forethought, destroyed by.