Chapter 7 LinkedList Challenges 5th problem has a more elegant solution

First I wanted to say how much I appreciate this book as it sparked an interest in me for data structures and algorithms which I never knew I had!

Anyway, I was able to figure out a nice solution for the 5th problem in chapter 7 which uses only one pointer instead of prev and current:

extension LinkedList where Value: Equatable {

    public mutating func removeAll(_ valueToRemove: Value) {
        while let head = head, head.value == valueToRemove {
            self.head = head.next
        }

        if head == nil {
            tail = nil
            return
        }

       // At this point, we're sure head.value is not equal to valueToRemove because of the head trimming
        var current = head

        while current?.next != nil {
           // If the next value matches, then remove the next node and do not move the current pointer
            if current?.next?.value == valueToRemove {
                current?.next = current?.next?.next
            } else {
                // otherwise, move the pointer one up
                current = current?.next
            }
        }

        tail = current
    }
}
1 Like