Add 1 to the Number in Linked List in Kotlin

by

To add 1 to a number represented as a linked list, we can traverse the linked list from the end (i.e., the least significant digit) to the beginning (i.e., the most significant digit), and perform the following steps:

  1. We start by adding 1 to the least significant digit (i.e., the last node in the list).
  2. If the sum is less than 10, we update the node value to the sum and we are done. Otherwise, we set the node value to 0 and carry over 1 to the next higher digit (i.e., the previous node in the list).
  3. We repeat step 2 for each higher digit until there are no more digits or we don’t need to carry over any more.

If we reach the beginning of the list and we still need to carry over 1, we create a new node with value 1 and insert it at the beginning of the list, making it the new head of the list.

Lets assume the Linked List representation in opposite order :

    Starting :            1->2->3
    After adding :    2->2->3

The Number was : 321 and we get : 322

Here’s a Kotlin implementation of this algorithm:

Kotlin
class Node(var value: Int, var next: Node? = null) {
    fun toList(): List<Int> {
        val result = mutableListOf<Int>()
        var curr: Node? = this
        while (curr != null) {
            result.add(curr.value)
            curr = curr.next
        }
        return result
    }
}
fun addOne(head: Node?): Node? {
    var curr = head
    var carry = 1
    // Traverse the list from the end
    while (curr != null) {
        val sum = curr.value + carry
        if (sum < 10) {
            curr.value = sum
            carry = 0
            break
        } else {
            curr.value = 0
            carry = 1
            curr = curr.next
        }
    }
    // If we still need to carry over 1, insert a new node at the beginning
    if (carry == 1) {
        val newHead = Node(1)
        newHead.next = head
        return newHead
    }
    return head
}
fun main() {
    // Create a linked list representing the number 123
    val head = Node(1)
    head.next = Node(2)
    head.next?.next = Node(3)
    println("Original list: ${head.toList()}")
    // Add 1 to the number represented by the list
    val newHead = addOne(head)
    // Print the original and new lists    
    println("New list: ${newHead?.toList()}")
}

Explanation of the addOne function:

  1. The function takes a linked list head as input, where each node in the list represents a digit in a non-negative integer in reverse order (i.e., the least significant digit is the first node, and the most significant digit is the last node).
  2. The function initializes a variable curr to point to the head of the list, and a variable carry to 1, because we want to add 1 to the least significant digit first.
  3. The function traverses the list from the end to the beginning, updating the node values and the carry variable as needed.
  4. At each node, the function adds the carry value to the node value to get the sum. If the sum is less than 10, the function updates the node value to the sum and sets carry to 0, because we don’t need to carry over to the next higher digit. If the sum is 10 or greater, the function sets the node value to 0 and sets carry to 1, because we need to carry over to the next higher digit.
  5. The function repeats step 4 for each node until there are no more nodes or we don’t need to carry over any more.
  6. If we reach the beginning of the list and we still need to carry over 1, the function creates a new node with value 1 and inserts it at the beginning of the list, making it the new head of the list.
  7. Finally, the function returns the modified list.

Here’s a summary of the time and space complexity of the addOne function:

  • Time complexity: O(n), where n is the number of nodes in the linked list. This is because we need to traverse the list once from the end to the beginning, and this operation takes linear time in the size of the list.
  • Space complexity: O(1), because we only use a constant amount of additional memory to store the curr and carry variables, regardless of the size of the input list. Therefore, the space used by the function does not depend on the size of the list, and it is considered constant.

Leave a Comment