单向链表
又称单链表,单链表中每个结点包含两部分,分别是数据域和指针域,上一个结点的指针指向下一结点,依次相连,形成链表。三个概念:首元结点、头结点和头指针,其中头结点在链表中不是必须的。
首元结点
就是链表中存储第一个元素的结点。
头结点
是在首元结点之前附设的一个结点,其指针域指向首元结点。头结点的数据域可以存储链表的长度或者其它的信息,也可以为空不存储任何信息。
头指针
是指向链表中第一个结点的指针。若链表中有头结点,则头指针指向头结点;若链表中没有头结点,则头指针指向首元结点。
链表与节点
引入单链表结构LinkList,仅保留头指针;与节点结构ListNode配合使用。头指针为空的单链表即为空链表,解决只使用节点结构不能构造空表的缺点。
type ListNode struct { data int next *ListNode } type LinkList struct { next *ListNode }
插入单个元素
头插法pushHead() 、 尾插法pushTail()
package main import "fmt" type ListNode struct { data int next *ListNode } type LinkList struct { next *ListNode } func (head *LinkList) pushHead(value int) { node := &ListNode{data: value} node.next = head.next head.next = node } func (head *LinkList) pushTail(value int) { node := &ListNode{data: value} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } func (node *ListNode) travel() { for node != nil { fmt.Print(node.data) node = node.next if node != nil { fmt.Print("->") } } fmt.Println("<nil>") } func (head *LinkList) travel() { head.next.travel() } func main() { nodes := &LinkList{} nodes.travel() nodes.pushTail(1) nodes.travel() nodes.pushHead(2) nodes.pushHead(3) nodes.travel() nodes.pushTail(4) nodes.pushTail(5) nodes.travel() } /*输出: <nil> 1<nil> 3->2->1<nil> 3->2->1->4->5<nil> */
数组插入链表
优化后插入多个元素:push()前插、append()追加
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) push(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) append(list []int) { for i := 0; i < len(list); i++ { node := &Node{data: list[i]} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } } func (head *List) travel() { node := head.next for node != nil { fmt.Print(node.data) node = node.next if node != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { node1 := &List{} node1.travel() node1.push([]int{1, 2, 3, 5}) node1.travel() node1.append([]int{7, 8, 9}) node1.travel() node1.push([]int{-2, -1, 0}) node1.travel() node2 := &List{} node2.travel() node2.append([]int{1, 2, 3, 5}) node2.travel() node2.push([]int{-2, -1, 0}) node2.travel() node2.append([]int{7, 8, 9}) node2.travel() } /*输出: <nil> 1->2->3->5<nil> 1->2->3->5->7->8->9<nil> -2->-1->0->1->2->3->5->7->8->9<nil> <nil> 1->2->3->5<nil> -2->-1->0->1->2->3->5<nil> -2->-1->0->1->2->3->5->7->8->9<nil> */
链表长度
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func Len(head *List) int { length := 0 for p := head.next; p != nil; p = p.next { length++ } return length } func (head *List) size() int { return Len(head) } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func main() { var node1, node2 *List node1 = new(List) node2 = new(List) fmt.Println(node1.size()) node1.build([]int{1, 2, 3, 5}) node2.build([]int{7, 8, 9}) fmt.Println(node1.size()) fmt.Println(Len(node2)) } /*输出: 0 4 3 */
链表副本
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) Copy() *List { p := head.next list := &List{} node := &Node{p.data, nil} tail := node for p = p.next; p != nil; p = p.next { var linknode = Node{data: p.data} (*tail).next = &linknode tail = &linknode } list.next = node return list } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) pushHead(value int) { node := &Node{data: value} node.next = head.next head.next = node } func (head *List) travel() { p := head.next for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { var node1, node2 *List node1 = new(List) node2 = new(List) node1.build([]int{1, 2, 3, 5}) node2 = node1 node3 := node1.Copy() //保存副本 node3.travel() node1.pushHead(0) node1.travel() node2.travel() node3.travel() //保存的副本不随node1变化 } /*输出: 1->2->3->5<nil> 0->1->2->3->5<nil> 0->1->2->3->5<nil> 1->2->3->5<nil> */
链表拼接
Cat()追加
与尾插单个元素类似;另外拼接链表的副本有好处的,不信可把.Copy()去掉试试。
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) Cat(node *List) { p := head.next q := node.Copy() //使用副本,确保node不变 if p != nil { for p.next != nil { p = p.next } p.next = q.next } else { head.next = q.next } } func (head *List) Copy() *List { p := head.next list := &List{} node := &Node{p.data, nil} tail := node for p = p.next; p != nil; p = p.next { var linknode = Node{data: p.data} (*tail).next = &linknode tail = &linknode } list.next = node return list } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) pushHead(value int) { node := &Node{data: value} node.next = head.next head.next = node } func (head *List) pushTail(value int) { node := &Node{data: value} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } func (head *List) travel() { p := head.next for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { var node1, node2 *List node1 = new(List) node2 = new(List) node1.build([]int{1, 2, 3, 5}) node2.build([]int{7, 8, 9}) node3 := &List{} node3.Cat(node1) node3.Cat(node2) node3.travel() node1.travel() node2.travel() } /*输出: 1->2->3->5->7->8->9<nil> 1->2->3->5<nil> 7->8->9<nil> */
Add()左加
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) Add(node *List) { q := node.Copy() p := q.next for p.next != nil { p = p.next } p.next = head.next head.next = q.next } func (head *List) Cat(node *List) { p := head.next q := node.Copy() if p != nil { for p.next != nil { p = p.next } p.next = q.next } else { head.next = q.next } } func (head *List) Copy() *List { p := head.next list := &List{} node := &Node{p.data, nil} tail := node for p = p.next; p != nil; p = p.next { var linknode = Node{data: p.data} (*tail).next = &linknode tail = &linknode } list.next = node return list } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) pushHead(value int) { node := &Node{data: value} node.next = head.next head.next = node } func (head *List) pushTail(value int) { node := &Node{data: value} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } func (head *List) travel() { p := head.next for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { var node1, node2 *List node1 = new(List) node2 = new(List) node1.build([]int{1, 2, 3, 5}) node2.build([]int{7, 8, 9}) node3 := &List{} node3.Add(node1) node3.travel() node3.Add(node2) node3.travel() node3.Add(node1) node3.travel() node3.Cat(node2) node3.travel() node1.travel() node2.travel() } /*输出: 1->2->3->5<nil> 7->8->9->1->2->3->5<nil> 1->2->3->5->7->8->9->1->2->3->5<nil> 1->2->3->5->7->8->9->1->2->3->5->7->8->9<nil> 1->2->3->5<nil> 7->8->9<nil> */
节点删除
节点删除需要判断链表自身是否为空链表,判断条件增加 if head.next == nil || p.next == nil {...}
删除首元结点
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) delHead() { p := head.next if head.next == nil || p.next == nil { head.next = nil } else { head.next = p.next } } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) travel() { for p := head.next; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { nodes := &List{} nodes.build([]int{1, 2, 3}) nodes.travel() nodes.delHead() nodes.travel() nodes.delHead() nodes.travel() nodes.delHead() nodes.travel() nodes.delHead() nodes.travel() } /*输出: 1->2->3<nil> 2->3<nil> 3<nil> <nil> <nil> */
删除尾结点
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) delTail() { p := head.next if head.next == nil || p.next == nil { head.next = nil } else { for p.next.next != nil { p = p.next } p.next = nil } } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) travel() { for p := head.next; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { nodes := &List{} nodes.build([]int{1, 2, 3}) nodes.travel() nodes.delTail() nodes.travel() nodes.delTail() nodes.travel() nodes.delTail() nodes.travel() nodes.delTail() nodes.travel() } /*输出: 1->2->3<nil> 1->2<nil> 1<nil> <nil> <nil> */
习题解答
1. 给定一个已排序链表,删除重复节点,原始链表中多次出现的数字只能保留一次。
示例1
输入: 1->1->2
输出: 1->2
示例2
输入: 1->1->2->3->3
输出: 1->2->3
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) removeDuplicates() { p := head.next node := &List{} data := p.data node.pushTail(data) for p != nil { if p.data != data { data = p.data node.pushTail(data) } p = p.next } head.next = node.next } func (head *List) pushTail(value int) { node := &Node{data: value} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) clear() { head.next = nil } func (head *List) travel() { for p := head.next; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println() //fmt.Println("<nil>") } func main() { nodes := &List{} nodes.build([]int{1, 1, 2}) nodes.travel() nodes.removeDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 1, 2, 3, 3}) nodes.travel() nodes.removeDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 2, 3, 3, 4, 4, 5}) nodes.travel() nodes.removeDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 1, 1, 2, 3, 3, 3}) nodes.travel() nodes.removeDuplicates() nodes.travel() } /*输出: 1->1->2 1->2 1->1->2->3->3 1->2->3 1->2->3->3->4->4->5 1->2->3->4->5 1->1->1->2->3->3->3 1->2->3 */
2. 给定一个排序链表,删除所有重复的节点,留原始链表有过重复的数字一个也不留。
示例1
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例2
输入: 1->1->1->2->3
输出: 2->3
package main import "fmt" type Node struct { data int next *Node } type List struct { next *Node } func (head *List) deleteDuplicates() { p := head.next node := &List{} if p.next == nil || p.data != p.next.data { node.pushTail(p.data) } if p.next != nil { data := p.data for p.next.next != nil { data = p.data p = p.next if data != p.data && p.data != p.next.data { node.pushTail(p.data) } } if p.data != p.next.data { node.pushTail(p.next.data) } } head.next = node.next } func (head *List) pushTail(value int) { node := &Node{data: value} p := head.next if p != nil { for p.next != nil { p = p.next } p.next = node } else { head.next = node } } func (head *List) build(list []int) { for i := len(list) - 1; i >= 0; i-- { node := &Node{data: list[i]} node.next = head.next head.next = node } } func (head *List) clear() { head.next = nil } func (head *List) travel() { for p := head.next; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("") //fmt.Println("<nil>") } func main() { nodes := &List{} nodes.build([]int{1, 1, 1, 2, 3}) nodes.travel() nodes.deleteDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 2, 3, 3, 4, 4, 5}) nodes.travel() nodes.deleteDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 1, 2, 3, 3, 4, 5}) nodes.travel() nodes.deleteDuplicates() nodes.travel() nodes.clear() nodes.build([]int{1, 2, 3, 3, 4, 5, 5}) nodes.travel() nodes.deleteDuplicates() nodes.travel() } /*输出: 1->1->1->2->3 2->3 1->2->3->3->4->4->5 1->2->5 1->1->2->3->3->4->5 2->4->5 1->2->3->3->4->5->5 1->2->4 */
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
1、递归法:
package main import "fmt" type Node struct { data int next *Node } type List struct { head *Node } //递归法合并有序链表 func recurMerge(p1 *Node, p2 *Node) *Node { if p1 == nil { return p2 } if p2 == nil { return p1 } p := new(Node) if p1.data < p2.data { p = p1 p.next = recurMerge(p1.next, p2) } else { p = p2 p.next = recurMerge(p1, p2.next) } return p } func (list *List) build(lst []int) { for i := len(lst) - 1; i >= 0; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) Copy() *List { p := list.head res := &List{} if p != nil { node := &Node{p.data, nil} q := node for p = p.next; p != nil; p = p.next { q.next = &Node{p.data, nil} q = q.next } res.head = node } return res } func (list *List) travel() { for p := list.head; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { List1 := &List{} List2 := &List{} List1.build([]int{1, 2, 4, 8}) List2.build([]int{1, 3, 3, 5, 5}) node1 := List1.Copy().head node2 := List2.Copy().head List0 := &List{} List0.head = recurMerge(node1, node2) List0.travel() List1.travel() List2.travel() //不使用副本的对比 node1 = List1.head node2 = List2.head List0 = &List{} List0.head = recurMerge(node1, node2) List0.travel() List1.travel() List2.travel() //另一组合并 List1 = &List{} List2 = &List{} List1.build([]int{0, 2, 4, 8}) List2.build([]int{1, 3, 5, 7, 9}) node1 = List1.Copy().head node2 = List2.Copy().head List0 = &List{} List0.head = recurMerge(node1, node2) List0.travel() List1.travel() List2.travel() } /*输出: 1->1->2->3->3->4->5->5->8<nil> 1->2->4->8<nil> 1->3->3->5->5<nil> 1->1->2->3->3->4->5->5->8<nil> 1->2->3->3->4->5->5->8<nil> 1->1->2->3->3->4->5->5->8<nil> 0->1->2->3->4->5->7->8->9<nil> 0->2->4->8<nil> 1->3->5->7->9<nil> */
本例中链表类的next指针改名为head:
type List struct { head *Node }
2、常规遍历:
1.
package main import "fmt" type Node struct { data int next *Node } type List struct { head *Node } func mergeLists(list1 *List, list2 *List) *List { list := &List{&Node{}} //初始赋值时多余一个默认值0 p := list.head p1 := list1.Copy().head //使用副本保留链表原样 p2 := list2.Copy().head for ; p1 != nil && p2 != nil; p = p.next { if p1.data < p2.data { p.next = p1 p1 = p1.next } else { p.next = p2 p2 = p2.next } } if p1 == nil { p.next = p2 } else if p2 == nil { p.next = p1 } list.head = list.head.next //去掉初始化时的0值 return list } func (list *List) build(lst []int) { for i := len(lst) - 1; i >= 0; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) Copy() *List { p := list.head res := &List{} if p != nil { node := &Node{p.data, nil} q := node for p = p.next; p != nil; p = p.next { q.next = &Node{p.data, nil} q = q.next } res.head = node } return res } func (list *List) travel() { for p := list.head; p != nil; p = p.next { fmt.Print(p.data) if p.next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { List1 := &List{} List2 := &List{} List1.build([]int{1, 2, 4, 8}) List2.build([]int{1, 3, 3, 5, 5}) List0 := mergeLists(List1, List2) List0.travel() List1.travel() List2.travel() List1 = &List{} List2 = &List{} List1.build([]int{0, 2, 4, 8}) List2.build([]int{1, 3, 5, 7, 9}) List0 = mergeLists(List1, List2) List0.travel() List1.travel() List2.travel() } /*输出: 1->1->2->3->3->4->5->5->8<nil> 1->2->4->8<nil> 1->3->3->5->5<nil> 0->1->2->3->4->5->7->8->9<nil> 0->2->4->8<nil> 1->3->5->7->9<nil> */