Add two number Represented by Linked List in Kotlin

by

To add two numbers represented by linked lists, you can follow these steps:

  1. Traverse the two linked lists simultaneously, starting from their heads.
  2. For each node, add the values of the nodes from the two linked lists, and keep track of the carry (if any).
  3. Create a new node with the sum (modulo 10) and set the carry to the next iteration.
  4. Attach the new node to the result linked list.
  5. If one of the linked lists ends before the other, just add the carry (if any) to the remaining linked list.
  6. If both linked lists end, but there is still a carry, create a new node with the value of the carry and attach it to the result linked list.

Lets assume the Linked List representation in opposite order :

    l1 :            2->4->3
    l2 :            5->6->4
    output:     7->0->8

l1 : 342 and l2 : 465 and we get : 807

Kotlin
class ListNode(var `val`: Int, var next: ListNode? = null)
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    var carry = 0
    var head: ListNode? = null
    var curr: ListNode? = null    
    var node1 = l1
    var node2 = l2  
    while (node1 != null || node2 != null || carry != 0) {
        val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
        val newNode = ListNode(sum % 10)
        carry = sum / 10
        
        if (head == null) {
            head = newNode
            curr = head
        } else {
            curr?.next = newNode
            curr = curr?.next
        }      
        node1 = node1?.next
        node2 = node2?.next
    }    
    return head
}
fun main() {
    // Create linked list 1: 2 -> 4 -> 3
    val l1 = ListNode(2, ListNode(4, ListNode(3)))
    
    // Create linked list 2: 5 -> 6 -> 4
    val l2 = ListNode(5, ListNode(6, ListNode(4)))
    
    // Add the two linked lists together: 2 -> 4 -> 3 + 5 -> 6 -> 4 = 7 -> 0 -> 8
    val result = addTwoNumbers(l1, l2)
    
    // Print the result: 7 -> 0 -> 8
    var node = result
    while (node != null) {
        print("${node.`val`} -> ")
        node = node.next
    }
    println("null")
}
  1. Declare and initialize carry, head, and curr variables. carry is the carry value from the previous iteration, head is the head node of the result linked list, and curr is the current node being processed in the result linked list.
  2. Declare node1 and node2 variables and set them to the heads of the two input linked lists.
  3. Start a while loop that continues as long as either node1 or node2 is not null, or there is still a carry value from the previous iteration.
  4. Inside the loop, calculate the sum of the current nodes’ values (or 0 if one of them is null) plus the carry value from the previous iteration.
  5. Create a new node with the value of the sum modulo 10 (since the maximum value of a node is 9) and set the carry value to the sum divided by 10.
  6. If head is null, set it to the new node, and set curr to head. Otherwise, set the next of curr to the new node, and set curr to the new node.
  7. Move node1 and node2 to their next nodes (if they exist) to continue processing.
  8. Return head, which is the head of the result linked list.

In the main function, we create two input linked lists and pass them to addTwoNumbers, then print out the values of the nodes in the result linked list.

Time complexity:

  • The function traverses both linked lists once in a single loop, performing a constant amount of work (e.g., integer addition and division) for each node.
  • Therefore, the time complexity is O(max(m,n)), where m and n are the lengths of the input linked lists.

Space complexity:

  • The function creates a new node for each digit in the output linked list, so the space required for the output linked list is proportional to the length of the output.
  • Additionally, the function uses a constant amount of extra space for variables such as carry, head, and curr.
  • Therefore, the space complexity is also O(max(m,n)), where m and n are the lengths of the input linked lists.

Leave a Comment