In the LeetCode Problem #2, we are given two numbers, with each digit represented in a node of the linked lists in reversed order. The task is to find the sum of those numbers and return the result in the form of a linked list again in reversed order.

For example; if the inputs are [1,2,3] and [4,5,6] then the actual numbers would be 321 and 654; their sum would be 975 and we should return a linked list [5,7,9]. We're given some constraints.

1. All the numbers would be non-negative numbers.
2. There won't be leading zeros; which means inputs won't have a digit 0 at the head of the lists.
3. The number of nodes in each of the lists would be from 1 to 100.
4. And finally, the values in each of the nodes will range from 0 to 9.

Solution

The solution for this problem is straightforward; we can traverse through the linked lists and then construct the original numbers. For example, if our list is [1,2,3] then we can construct our original number 321 with a simple logic as used in the pseudocode below.

function findReverseNumber(headNode *LinkNode):
  originalNum := 0
  node := headNode
  while(node neq null) {
    originalNum = originalNum*10 + node.value
    node = node.next()
  }
  return originalNum
end function

Now we can modify this pseudocode to simultaneously traverse through both lists and get two numbers in one go. Then we can sum up two numbers to get our results. We can use modulo division to reverse the number and construct our final linked list. Finally, we will return the head node.

function addTwoNumbers(headNode1, headNode2 *LinkNode):
  originalNum1 := 0
  originalNum1 := 0

  node_1 := headNode1
  noide_2 := headNode2

  // traversing through two nodes
  while(node_1 neq null or node_2 neq null) {

    if (node_1 neq null){
      originalNum1 = originalNum1*10 + node_1.value
      node_1 = node_1.next()
    }

    if (node_2 neq null){
      originalNum2 = originalNum2*10 + node_2.value
      node_2 = node_2.next()
    }

  }
  sum := originalNum1 + originalNum2
  digit := sum %10
  head := ListNode
  head.value = digit
  head.next = null
  sum = (sum - digit) / 10 

  nextNode = head
  while (sum / 10 neq 0) {
    newNode := ListNode
    digit := sum %10
    sum = (sum - digit) / 10 
    newNode.value = digit
    nextNode.next = newNode
    nextNode = newNode
  }

  return head

end function

The solution above has O(2n), where n = max(list1.length, list2.length); time complexity. While implementing this logic in GO lang, we will have to take care of one more problem; the length of the lists. They could go up to 100 nodes in length; which means in our approach of generating the original number from the linked list using number = number*10 + node.value can create a huge intermediate number of order 10¹⁰⁰. To mitigate this, we can use the big library package available with go installation. The complete solution to this problem in the go programming language is as below.

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    sumOfFirstNode := big.NewInt(0)
    sumOfSecondNode := big.NewInt(0)
    mul := big.NewInt(1)
    ten := big.NewInt(10)
    for {
        if l1 == nil && l2 == nil {
            break
        }

        if l1 != nil {
        sumOfFirstNode = big.NewInt(0).Add(big.NewInt(0).Mul(mul, big.NewInt(int64(l1.Val))), sumOfFirstNode)
            l1 = l1.Next
        }

        if l2 != nil {
        sumOfSecondNode = big.NewInt(0).Add(big.NewInt(0).Mul(big.NewInt(int64(l2.Val)), mul), sumOfSecondNode)
            l2 = l2.Next
        }

      mul = big.NewInt(0).Mul(mul, big.NewInt(10))
    }
    sum := big.NewInt(0).Add(sumOfFirstNode, sumOfSecondNode)
    modTen := big.NewInt(0).Mod(sum, ten)
    node := &ListNode{
        Val:  int(modTen.Int64()),
        Next: nil,
    }

    nextNode := node

    sum = big.NewInt(0).Div(big.NewInt(0).Sub(sum, modTen), ten)
    for sum.Cmp(big.NewInt(0)) > 0 {
        modTen := big.NewInt(0).Mod(sum, ten)
        nextNode.Next = &ListNode{
            Val:  int(modTen.Int64()),
            Next: nil,
        }
        sum = big.NewInt(0).Div(big.NewInt(0).Sub(sum, modTen), ten)
        nextNode = nextNode.Next
    }

    return node
}

Although, this solution is pretty efficient and works well; still there is some space for improvement. One clean approach is to generate our result linked-list while traversing the input lists. It will create an efficient solution with O(n) time complexity and remove some intermediate calculations. It will also prevent the usage of big library because summing up two single-digit numbers results in a double-digit number at max. The implementation of the new solution is left for the readers to complete.