LeetCode Playground

leetCode.swift

// Problem 1290: Convert Binary Number in a Linked List to Integer
// Link: https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer
// Solution 1: using an array to store the values, multiply each value by its bit later
func getDecimalValue(_ head: ListNode?) -> Int {
    if head == nil { return 0 }

    var headCopy = head
    // an array stores all the values
    var vals = [Int]()
    var bit = 1
    while let h = headCopy {
        vals.append(h.val)
        bit *= 2
        headCopy = h.next
    }

    // iterate over the values, 
    // for each value multiply it with the its bit and add to the sum
    return vals.reduce(0, { (sum, val) -> Int in
        bit /= 2
        return sum + val*bit
    })
}

// Solution 2: bit shifting
func getDecimalValue(_ head: ListNode?) -> Int {
    if head == nil { return 0 }

    var headCopy = head
    var sum = 0
    while let h = headCopy {
        sum = sum << 1
        sum += h.val
        headCopy = h.next
    }

    return sum
}


/****************************************************************/
// Problem: 876: Middle of the Linked List 
// Link: https://leetcode.com/problems/middle-of-the-linked-list/
// Solution 1: traverse through the list to get the length, then calculate the mid index,
// traverse again and keep moving the head til index to get the result
func middleNode(_ head: ListNode?) -> ListNode? {
    if head == nil { return nil }

    var headCopy = head

    // calculate the length of the List
    var count = 0
    while let h = headCopy {
        count += 1
        headCopy = h.next
    }

    let mid = count / 2
    // traverse until the mid index, then return the head
    var headResult = head
    for i in 0..<mid {
        headResult = headResult!.next
    }

    return headResult
}

// Solution 2: Have 2 heads, 
// 1 slow-running head: result head
// 1 fast-running head: traversing to the end
func middleNode(_ head: ListNode?) -> ListNode? {
    if head == nil { return nil }
    if head!.next == nil { return head }

    var headCopy = head
    var headResult = head
    var count = 1

    while headCopy != nil && headCopy!.next != nil {
        // slow runner
        if count % 2 == 1 {
            headResult = headResult!.next
        }
        // fast runner
        headCopy = headCopy!.next
        count += 1
    }

    return headResult
}