链表
一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单链表结构
利用 struct 可以包容多种数据类型，结构体内也可以包含多个成员，这些成员可以是基本类型、自定义类型、数组类型，也可以是指针类型。这里可以使用指针类型成员来存放下一个结点的地址。如以下定义，成员 data 用来存放结点中的数据(整数类型)，next 是指针类型的成员，它指向 ListNode struct 类型数据，也就是下一个结点的数据类型。
1. type ListNode struct { 2. data int 3. next *ListNode 4. }
创建节点
节点声明和赋值有以下几种格式：
package main import "fmt" type ListNode struct { data int next *ListNode } func main() { var head *ListNode head = new(ListNode) head.data = 1 var node1 = new(ListNode) node1.data = 2 var node2 = &ListNode{3, nil} var node3 = &ListNode{data: 4} fmt.Println(*head) fmt.Println(*node1) fmt.Println(*node2) fmt.Println(*node3) } /* 输出： {1 <nil>} {2 <nil>} {3 <nil>} {4 <nil>} */
遍历链表
一个for循环即可，结构描述的链表没有空链表的，不论data是何种类型，一旦声明即使不马上赋值也会有类型默认值，比如new(ListNode)即赋值了ListNode{0, nil}。
func showNode(p *ListNode) { fmt.Print(*p) for p.next != nil { p = p.next fmt.Print("->", *p) } fmt.Println() }
头插法
新结点放在链表的最前面
package main import "fmt" type ListNode struct { data int next *ListNode } func showNode(p *ListNode) { fmt.Print(*p) for p.next != nil { p = p.next fmt.Print("->", *p) } fmt.Println() } func main() { var head = &ListNode{0, nil} for i := 1; i < 5; i++ { var node = ListNode{data: i} node.next = head head = &node } showNode(head) } /* 输出： {4 0xc000084250}->{3 0xc000084240}->{2 0xc000084230}->{1 0xc000084220}->{0 <nil>} */
尾插法
新结点追加到链表的最后面
package main import "fmt" type ListNode struct { data int next *ListNode } func showNode(p *ListNode) { fmt.Print(*p) for p.next != nil { p = p.next fmt.Print("->", *p) } fmt.Println() } func main() { var head, tail *ListNode head = &ListNode{0, nil} tail = head for i := 1; i < 5; i++ { var node = ListNode{data: i} (*tail).next = &node tail = &node } showNode(head) } /* 输出： {0 0xc000084220}->{1 0xc000084230}->{2 0xc000084240}->{3 0xc000084250}->{4 <nil>} */
遍历方法
方法的定义：参数表放在函数名前
package main import "fmt" type ListNode struct { data int next *ListNode } func (p *ListNode) travel() { fmt.Print(p.data) for p.next != nil { p = p.next fmt.Print("->", p.data) } fmt.Println("<nil>") } func main() { var head = &ListNode{0, nil} head.travel() for i := 1; i < 10; i++ { var node = ListNode{data: i} node.next = head head = &node } head.travel() var root *ListNode root = new(ListNode) root.travel() } /* 输出： 0<nil> 9->8->7->6->5->4->3->2->1->0<nil> 0<nil> */
链表长度
注意：函数与方法的区别
package main import "fmt" type ListNode struct { data int next *ListNode } func (head *ListNode) size() int { size := 1 for head = head.next; head != nil; size++ { head = head.next } return size } func Len(head *ListNode) int { size := 1 for head = head.next; head != nil; size++ { head = head.next } return size } func main() { var head = &ListNode{0, nil} fmt.Println(Len(head)) fmt.Println(head.size()) for i := 1; i < 10; i++ { var node = ListNode{data: i} node.next = head head = &node } fmt.Println(Len(head)) fmt.Println(head.size()) } /* 输出： 1 1 10 10 */
链表转数组
package main import ( "fmt" ) type ListNode struct { data int next *ListNode } func (head *ListNode) size() int { size := 1 for head = head.next; head != nil; size++ { head = head.next } return size } func (head *ListNode) tolist() []int { var res []int res = make([]int, 0, head.size()) for head.next != nil { res = append(res, head.data) head = head.next } res = append(res, head.data) return res } func (head *ListNode) tolist2() []int { var res []int res = make([]int, 0, head.size()) res = append(res, head.data) head = head.next for head != nil { res = append(res, head.data) head = head.next } return res } func main() { var head = &ListNode{0, nil} for i := 1; i < 10; i++ { var node = ListNode{data: i} node.next = head head = &node } fmt.Println(head.tolist()) var root, tail *ListNode root = &ListNode{0, nil} tail = root for i := 1; i < 10; i++ { var node = ListNode{data: i} (*tail).next = &node tail = &node } fmt.Println(root.tolist2()) } /* 输出： [9 8 7 6 5 4 3 2 1 0] [0 1 2 3 4 5 6 7 8 9] */
数组转链表
package main import "fmt" type ListNode struct { data int next *ListNode } func (p *ListNode) travel() { fmt.Print(p.data) for p.next != nil { p = p.next fmt.Print("->", p.data) } fmt.Println("<nil>") } func toNode(list []int) *ListNode { var head, tail *ListNode head = &ListNode{list[0], nil} tail = head for i := 1; i < len(list); i++ { var node = ListNode{data: list[i]} (*tail).next = &node tail = &node } return head } func main() { var lst = []int{1, 3, 2, 3, 5, 6, 6, 8, 9} toNode(lst).travel() } /* 输出： 1->3->2->3->5->6->6->8->9<nil> */
例题
实战一：
给定一个已排序链表，删除重复节点，原始链表中多次出现的数字只能保留一次。
示例1
输入: 1->1->2
输出: 1->2
示例2
输入: 1->1->2->3->3
输出: 1->2->3
实战二：
给定一个排序链表，删除所有重复的节点，留原始链表有过重复的数字一个也不留。
示例1
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例2
输入: 1->1->1->2->3
输出: 2->3
实战三：
给定两个有序链表(升序)，合并为一个新的有序链表并返回。
示例1
输入：1->2>4->8
1->3->3->5->5
输出：1->1->2->3->3->4->5->5->8
示例2
输入：0->2>4->8
1->3->5->7->9
输出：0->1->2->3->4->5->6->7->8->9
