LC: 2: Add two Numbers

Solution 1 – Intuition 1 (BAD)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   
    //Initialize revslice1 & revslice2 for two nos
    var revslice1, revslice2 []int
    
    currentNode := l1    
    // Loop & Traverse l1 add elements to revslice1     
    for {        
        revslice1 = append(revslice1,currentNode.Val)        
        if currentNode.Next ==nil{
            break
        }                
        currentNode = currentNode.Next
    }


    currentNode = l2
    // Loop & Traverse l2 add elements to revslice2
    for {        
        revslice2 = append(revslice2,currentNode.Val)        
        if currentNode.Next ==nil{
            break
        }                
        currentNode = currentNode.Next                
    }

    //Initialize str1, str2
    var str1, str2 string
    
    // Loop & add append digit to str1 from revslice1 
    for i:=0;i<len(revslice1);i++{
        str1+= fmt.Sprintf("%d",revslice1[i])
    }

    // Loop & add append digit to str2 from revslice2    
    for i:=0;i<len(revslice2);i++{
        str2+= fmt.Sprintf("%d",revslice2[i])
    }
    

    //calc sumStr
    var sumStr string
    sl1 := len(str1)
    sl2 := len(str2)
    maxLen := sl1
    if sl1<sl2{
        maxLen = sl2
    }
    
    var carry int
    for i:=0;i<maxLen;i++{
        var d1,d2,d3 int
        if i <sl1 {
            d1,_ = strconv.Atoi(string(str1[i]))
        }

        if i <sl2 {
            d2,_ = strconv.Atoi(string(str2[i]))
        }
        
        d3 = d1+d2
        if carry>0 {
            d3+=1
            carry = 0
        }
        if d3 > 9{
            carry = 1            
            sumStr+=fmt.Sprintf("%d",d3%10)
        } else {
            sumStr+=fmt.Sprintf("%d",d3)

        }                
    }

    if carry>0{
        sumStr+=fmt.Sprintf("%d",1)
    }
    strRes := sumStr
            
    // Loop & create a new LinkedList ListNodeRes
    var resNode, prevNode *ListNode
    for i:=0;i<len(strRes);i++{
        char := string(strRes[i])
        val,_ := strconv.Atoi(char)

         newNode := &ListNode{Val:val,}        

        if i==0{
            resNode = newNode
            prevNode = newNode
        } else {
            prevNode.Next = newNode
            prevNode = newNode
        }
    }
    

    return resNode
    
}

Possible optimisations to try

Skip string conversion to reverse the digits, just keep them in arrays and reverse
Try with a place value instead of carry digit approach
Try creating result node while traversing and adding new sum Nodes, save carry to next node

Solution 2 – Same intuition small optimisation (BAD)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   
    //Initialize revslice1 & revslice2 for two nos
    var revslice1, revslice2 []int
    
    currentNode := l1    
    // Loop & Traverse l1 add elements to revslice1     
    for {        
        revslice1 = append(revslice1,currentNode.Val)        
        if currentNode.Next ==nil{
            break
        }                
        currentNode = currentNode.Next
    }


    currentNode = l2
    // Loop & Traverse l2 add elements to revslice2
    for {        
        revslice2 = append(revslice2,currentNode.Val)        
        if currentNode.Next ==nil{
            break
        }                
        currentNode = currentNode.Next                
    }

    //Initialize x1, x2
    var x1, x2 []int
    
    // Loop & add append digit to x1 from revslice1 
    for i:=0;i<len(revslice1);i++{
        x1=append(x1,revslice1[i])
    }

    // Loop & add append digit to x2 from revslice2    
    for i:=0;i<len(revslice2);i++{
        x2=append(x2,revslice2[i])
    }
    

    //calc sumNos
    var sumNos []int
    sl1 := len(x1)
    sl2 := len(x2)
    maxLen := sl1
    if sl1<sl2{
        maxLen = sl2
    }
    
    var carry int
    for i:=0;i<maxLen;i++{
        var d1,d2,d3 int
        if i <sl1 {
            d1 = x1[i]
        }

        if i <sl2 {
            d2 = x2[i]
        }
        
        d3 = d1+d2
        if carry>0 {
            d3+=1
            carry = 0
        }
        if d3 > 9{
            carry = 1            
            sumNos = append(sumNos,d3%10)
        } else {
            sumNos = append(sumNos,d3)

        }                
    }

    if carry>0{
        sumNos=append(sumNos,1)
    }    
            
    // Loop & create a new LinkedList ListNodeRes
    var resNode, prevNode *ListNode
    for i:=0;i<len(sumNos);i++{            
        newNode := &ListNode{Val:sumNos[i],}        
        if i==0{
            resNode = newNode
            prevNode = newNode
        } else {
            prevNode.Next = newNode
            prevNode = newNode
        }
    }    

    return resNode    
}

Solution 3 – Intuition 2 : Single loop (Better – O(max(L1,L2)))

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { 
    var resList,prevNode *ListNode
    var sum,carry int

    for l1!=nil || l2!=nil  {
        if l1==nil{
            l1 = &ListNode{Val:0}
        }
        if l2==nil{
            l2 = &ListNode{Val:0}
        }
        sum = l1.Val+l2.Val+carry
        carry=0
        
        newNode := ListNode{Val:sum%10,}
        if sum/10>0{
            carry=1
        }
        if resList==nil{            
            resList=&newNode
            prevNode=resList
            l1=l1.Next
            l2=l2.Next
            continue
        }
     
        prevNode.Next=&newNode
        prevNode=&newNode        
        l1=l1.Next
        l2=l2.Next
    }

    if carry>0{        
        prevNode.Next = &ListNode{Val:1}
    }    

    return resList    
}