82. Remove Duplicates from Sorted List II #

package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1
func deleteDuplicates1(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}
	newHead := &ListNode{Next: head, Val: -999999}
	cur := newHead
	last := newHead
	front := head
	for front.Next != nil {
		if front.Val == cur.Val {
			// fmt.Printf("same node front = %v | cur = %v | last = %v\n", front.Val, cur.Val, last.Val)
			front = front.Next
			continue
		} else {
			if cur.Next != front {
				// fmt.Printf("delete duplicate nodes front = %v | cur = %v | last = %v\n", front.Val, cur.Val, last.Val)
				last.Next = front
				if front.Next != nil && front.Next.Val != front.Val {
					last = front
				}
				cur = front
				front = front.Next
			} else {
				// fmt.Printf("before regular loop front = %v | cur = %v | last = %v\n", front.Val, cur.Val, last.Val)
				last = cur
				cur = cur.Next
				front = front.Next
				// fmt.Printf("after regular loop front = %v | cur = %v | last = %v\n", front.Val, cur.Val, last.Val)

			}
		}
	}
	if front.Val == cur.Val {
		// fmt.Printf("same node front = %v | cur = %v | last = %v\n", front.Val, cur.Val, last.Val)
		last.Next = nil
	} else {
		if cur.Next != front {
			last.Next = front
		}
	}
	return newHead.Next
}

// Solution 2
func deleteDuplicates2(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	if head.Next != nil && head.Val == head.Next.Val {
		for head.Next != nil && head.Val == head.Next.Val {
			head = head.Next
		}
		return deleteDuplicates(head.Next)
	}
	head.Next = deleteDuplicates(head.Next)
	return head
}

func deleteDuplicates(head *ListNode) *ListNode {
	cur := head
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}
	for cur.Next != nil {
		if cur.Next.Val == cur.Val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return head
}

// Solution 3 Simple double-loop solution O(n*m)
func deleteDuplicates3(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	nilNode := &ListNode{Val: 0, Next: head}
	head = nilNode

	lastVal := 0
	for head.Next != nil && head.Next.Next != nil {
		if head.Next.Val == head.Next.Next.Val {
			lastVal = head.Next.Val
			for head.Next != nil && lastVal == head.Next.Val {
				head.Next = head.Next.Next
			}
		} else {
			head = head.Next
		}
	}
	return nilNode.Next
}

// Solution 4 Two pointers + deletion flag, single-loop solution O(n)
func deleteDuplicates4(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	nilNode := &ListNode{Val: 0, Next: head}
	// Flag indicating whether there was a delete operation in the previous traversal
	lastIsDel := false
	// Dummy empty node
	head = nilNode
	// Front and back pointers used for comparison
	pre, back := head.Next, head.Next.Next
	// Each time, delete only the earlier duplicate element, leaving one for duplicate checking in the next traversal
	// The update positions and value comparison for the pre and back pointers are important and clever
	for head.Next != nil && head.Next.Next != nil {
		if pre.Val != back.Val && lastIsDel {
			head.Next = head.Next.Next
			pre, back = head.Next, head.Next.Next
			lastIsDel = false
			continue
		}

		if pre.Val == back.Val {
			head.Next = head.Next.Next
			pre, back = head.Next, head.Next.Next
			lastIsDel = true
		} else {
			head = head.Next
			pre, back = head.Next, head.Next.Next
			lastIsDel = false
		}
	}
	// Handle the case like [1,1], where one node remains after deletion
	if lastIsDel && head.Next != nil {
		head.Next = nil
	}
	return nilNode.Next
}