4.1 链表基础

链表中每个节点包含指向下一节点的指针, 这些指针将节点连成链状结构.

链表的内存分配是动态的, 创建链表时无需知道链表的长度. 链表的内存不需要在创建时一次性分配, 而是插入一个节点时分配一次内存.

链表的插入操作时间为 O(1), 而链表的查询时间为 O(n).

单向链表的节点可定义为:

type ListNode struct {
    Val int
    Next *ListNode
}

Reference

1. 剑指Offer（专项突破版）