Go language power buckle brush – add two numbers | Go theme months

The first time to write Go list Pointers, successfully compiled, open!!

2. Add two numbers

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

You can assume that neither of these numbers will start with 0, except for the number 0.

Input: l1 = [2, 3], l2 =,6,4 [5] output:,0,8 [7] : 342 + 465 = 807.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ad… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The code that passes the first compilation

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var head = new(ListNode)
    var movePoint = head
    head.Val = 0
    carry := 0
    l1point:=l1
    l2point:=l2
    for; l1point ! =nil|| l2point ! =nil;  {
        sum := 0
        ifl1point ! =nil {
            sum += l1point.Val
        }
        ifl2point ! =nil {
            sum += l2point.Val
        }
        sum += carry
        movePoint.Val = sum % 10
        carry = sum / 10
        movePoint.Next  = new(ListNode)
        movePoint = movePoint.Next
        
        l1point = l1point.Next
        l2point = l2point.Next
    } 
    if carry > 0 {
        movePoint.Val = carry
    } else {
        MovePoint =nil if a->b->c->d and movePoint is to d, setting movePoint=nil does not remove the last contact, setting c. ext =nil */
        movePoint = nil
    }

    return head
}
Copy the code

Problems encountered:

1. Compile pass: well, the first time write go list, compile pass, open son!
2. The test case failed: [2,4,3] + [5,6,4], the correct result should be [7, 0, 8], but the running result is [7, 0, 8, 0], that is, the first part of the code annotation: the linked list removes nodes incorrectly

Add tail node, move pointer always next to tail node, fix first error, code as follows:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var head = new(ListNode)
    var movePoint = head
    var tail = head
    head.Val = 0
    carry := 0
    l1point:=l1
    l2point:=l2
    for; l1point ! =nil|| l2point ! =nil;  {
        sum := 0
        ifl1point ! =nil {
            sum += l1point.Val
        }
        ifl2point ! =nil {
            sum += l2point.Val
        }
        sum += carry
        movePoint.Val = sum % 10
        carry = sum / 10
        movePoint.Next  = new(ListNode)
        tail = movePoint
        movePoint = movePoint.Next

        /* Error: Len (l1) and len(l2) are not equal */
        l1point = l1point.Next
        l2point = l2point.Next
    } 
    if carry > 0 {
        movePoint.Val = carry
        tail = movePoint
    } else {
        tail.Next = nil
    }

    return head
}
Copy the code

[9,9,9,9, 9,9,9,9]+ [9,9,9,9]

**Line 38: panic: runtime error: invalid memory address or nil pointer dereference**
Copy the code

Program logic error: the condition of the loop is that neither of the two lists given is empty, so the next node should be null. Or null when the value is retrieved. After the second modification, the code is as follows:

type ListNode struct {
    Val int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var head = new(ListNode)
    var movePoint = head
    var tail = head
    head.Val = 0
    carry := 0
    l1point:=l1
    l2point:=l2
    for; l1point ! =nil|| l2point ! =nil;  {
        sum := 0
        ifl1point ! =nil {
            sum += l1point.Val
            /* Move the node back here l1point*/
            l1point = l1point.Next
        }
        ifl2point ! =nil {
            sum += l2point.Val
            /* Move node L2Point backward here */
            l2point = l2point.Next
        }
        sum += carry
        movePoint.Val = sum % 10
        carry = sum / 10
        movePoint.Next  = new(ListNode)
        tail = movePoint
        movePoint = movePoint.Next
    } 
    if carry > 0 {
        /* Carry reserved */
        movePoint.Val = carry
        tail = movePoint
    } else {
        /* Discard the last node */
        tail.Next = nil
    }
    return head
}
Copy the code

After checking the basic syntax of Go, I moved some statements to the initialization statement (init section) and circular execution statement (POST section) of for. The revised final version:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var head = new(ListNode)
    var movePoint = head
    var tail = head
    head.Val = 0
    carry := 0
    forl1point, l2point :=l1, l2; l1point ! =nil|| l2point ! =nil; tail, movePoint = movePoint, movePoint.Next {
        sum := 0
        ifl1point ! =nil {
            sum += l1point.Val
            l1point = l1point.Next
        }
        ifl2point ! =nil {
            sum += l2point.Val
            l2point = l2point.Next
        }
        sum += carry
        movePoint.Val = sum % 10
        carry = sum / 10
        movePoint.Next  = new(ListNode)
    } 
    if carry > 0 {
        movePoint.Val = carry
        tail = movePoint
    } else {
        tail.Next = nil
    }

    return head
}
Copy the code