Personal evaluation: linked list type questions… The difficulty lies in pointer and head and tail processing, debugging is really difficult 😂

Simple questions: 🌟 🌟 (reference LeeCode 🌟, moderate 🌟 🌟, 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)

Delete duplicate element II from sorted linked list

Topic describes

Delete duplicate element II from sorted list

There is a linked list in ascending order, and you are given the head node of the linked list. Please delete all the nodes in the linked list that have duplicate numbers, and only keep the original list that does not have duplicate numbers.

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

Example 1:

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

Output:,2,5 [1]

Example 2:

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

Output: [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

The idea of traversal is as follows:

  • Compare current value with subsequent value, different = “continue (sorted, can determine unique)
  • Compare the current value with the subsequent value, same = “continue the loop to determine whether the value is the same as that of the next node

Note the addition of sentinel/dummy nodes for possible header deletion processing

There is an internal loop, so recursion can be considered. I think it is unnecessary to introduce this problem, which will increase the complexity of understanding

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

  	// Introduce sentry/dummy nodes to make header deletion easier
    dummy := &ListNode{0, head}

    cur := dummy
    forcur.Next ! =nil&& cur.Next.Next ! =nil {
        if cur.Next.Val == cur.Next.Next.Val {
            x := cur.Next.Val
            forcur.Next ! =nil && cur.Next.Val == x { // Iterate until different
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }

    return dummy.Next
}
Copy the code

extended

Wrong at first… It is a sorted list, so the Hash record is used, and only the duplicate number is deleted, like uniq, without deleting the duplicate number itself. 😂)

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	prev := head
	curr := head
	nMap := make(map[int]bool)
	forcurr.Next ! =nil {
		next := curr.Next
		if _, ok := nMap[curr.Val]; ok { // If yes, delete the node
			*curr = *curr.Next // Delete list node (not tail)
			continue
		}
		nMap[curr.Val] = true
		prev = curr
		curr = next
	}
	if _, ok := nMap[curr.Val]; ok { // End node deleted, special handling
		prev.Next = nil
	}
	return head
}
Copy the code

conclusion

Sentinel nodes are very useful for linked list problems. In addition, the problem read several times 😂