插入一个简单的单链表

Question

I am trying to solve leetcode problem in Go to teach myself the language. I have a single linked list and an insert function:

type ListNode struct {
    Val int
    Next * ListNode
}


func Insert(listNode * ListNode, i int) {
    // @fixme how to check the first node?
    if listNode == nil {
        listNode.Val = i
        listNode.Next = nil
    } else {
        for;;
        listNode = listNode.Next {
            if listNode.Next == nil {
                listNode.Next = & ListNode {
                    i, nil
                }
                break
            }
        }
    }
}

func main() {

    vals: = [] int {
            1, 2, 3, 4, 5
        }
    var list ListNode
    for _,
    i: = range vals {
        Insert( & list, i)
    }
}

The problem is that when an instance of ListNode is instantiated the struct fields have zero values and I am unable update the set first element of the list because I am unable to check for it. In other words, that a ListNode item is initialized but empty. So when I want build a list 1->2->3->4->5 I end up having: 0->1 ->2 ...5 . The limitation is that I cannot change the struct definition as leetcode have that already defined. Here is a working example of the code above: https://play.golang.org/p/bIz-VjY1PS7

Answer 1

What you should do is that you shouldn't use ListNode you should be using *ListNode, that way an empty list is represented by a nil *ListNode:

func New() *ListNode {
    return nil
}

func Insert(listNode *ListNode, i int) *ListNode {
    // If it's nil, create it
    if listNode == nil {
        listNode = &ListNode{i, nil}
    } else {
        l := listNode
        for ; l.Next != nil; l = l.Next {
        }
        l.Next = &ListNode{i, nil}
    }
    return listNode
}