Leetcode: 2487. Remove Nodes From Linked List.

removeNodes.go

// Leetcode: 2487. Remove Nodes From Linked List.
// https://leetcode.com/problems/remove-nodes-from-linked-list/
// = = = = = = = = = = = = = =
// Accepted.
// Thanks God, Jesus Christ!
// = = = = = = = = = = = = = =
// Runtime: 284 ms, faster than 7.94% of Go online submissions for Remove
// Nodes From Linked List.
// Memory Usage: 13.8 MB, less than 44.44% of Go online submissions for Remove
// Nodes From Linked List.
// 2024.05.06 Daily Challenge.

package main

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

// 1. Save list into the slice.
// 2. Nil all pointers.
// 3. Move that slice right to left, mark elements to delete.
// 4. Create a fake head and select unmarked elements.
func removeNodes(head *ListNode) *ListNode {
	// 1. List to slice.
	nodes := make([]*ListNode, 0)
	tmp := head
	for tmp != nil {
		nodes = append(nodes, tmp)
		tmp = tmp.Next
	}
	// 2. Nill all pointers.
	for _, v := range nodes {
		v.Next = nil
	}
	// 3. Create a marks array.
	deleted := make([]bool, len(nodes))
	// 4. Move right to left, mark elements for delete.
	max := nodes[len(nodes)-1].Val
	for j := len(nodes) - 1; j >= 0; j -= 1 {
		if nodes[j].Val < max {
			deleted[j] = true
		} else {
			max = nodes[j].Val
		}
	}
	// 5. Aggregate a new list.
	fakeHead := &ListNode{}
	tail := fakeHead
	for i, v := range deleted {
		if !v {
			tail.Next = nodes[i]
			tail = tail.Next
		}
	}
	return fakeHead.Next
}