2181.merge-nodes-in-between-zeros.md

2181. Merge Nodes in Between Zeros

Recursive

/**
 * For each zero node, we iterate the next node until we meet the next zero node. Then we create a new node with the sum of the current node and call merge() with the next node of the zero node.
 */
fun mergeNodes(head: ListNode?): ListNode? {
    if (head == null || head.next == null) return null
    // It should be non-zero node or null (end of the list)
    var current = head.next

    // Iterate to sum the non-zero node until we meet the next zero node
    var sum = 0
    while (current != null && current.`val` != 0) {
        sum += current.`val`
        current = current.next
    }
    val mergedNode = ListNode(sum)
    mergedNode.next = mergeNodes(current)
    return mergedNode
}

// Same idea with helper function
fun mergeNodes(head: ListNode?): ListNode? {
        if (head == null) return null
    return merge(head.next)
}

fun merge(head: ListNode?): ListNode? {
    if (head == null) return null
    var current: ListNode? = head
    var sum = 0
    while (current != null && current.`val` != 0) {
        sum += current.`val`
        current = current.next
    }
    val sumNode = ListNode(sum)
    sumNode.next = merge(current?.next)
    return sumNode
}

// Or equivalently, but it's a bit more complex.

fun mergeNodes(head: ListNode?): ListNode? {
    if (head == null) return null
    return merge(ListNode(0), head.next)
}

/**
 * We check the current node, if the current node is 0, then we create a new node with the sum of the merged node and call merge() with the next node of the zero node.
 */
private fun merge(merged: ListNode, current: ListNode?): ListNode? {
    if (current == null) return null
    if (current.`val` == 0) {
        merged.next = merge(ListNode(0), current.next)
        return merged
    } else {
        merged.`val` += current.`val`
        return merge(merged, current.next)
    }
}

Iterative

It guarantees that the beginning and end of the list are always zeros, and there is no adjacent zero nodes. We can start from the next node of head, iterate the node to sum until we meet the next zero node. Then we create a new node with the sum and connect it to the merged list. We continue the process until we reach the end of the list.

0 -> x -> ... -> y -> 0 -> ...
     c
     sum += x
                      c
                      sum = 0
sentinel -> (x + ... + y)

fun mergeNodes(head: ListNode?): ListNode? {
    val sentinel = ListNode(-1)
    sentinel.next = head
    var merge = sentinel
    var current: ListNode? = head?.next // Skip the first zero node
    var sum = 0
    while (current != null) {
        if (current.`val` == 0) {
            merge.next = ListNode(sum)
            merge = merge.next!!
            sum = 0
        } else {
            sum += current.`val`
        }
        current = current.next
    }
    return sentinel.next
}