单链表——刷题实战
任意类型的数据域
之前的链表定义数据域都是整型int，如果需要不同类型的数据就要用到 interface{}。
空接口 interface{}
对于描述起不到任何的作用(因为它不包含任何的method），但interface{}在需要存储任意类型的数值的时候相当有用，因为它可以存储任意类型的数值。
一个函数把interface{}作为参数，那么它可以接受任意类型的值作为参数；如果一个函数返回interface{}，那么也就可以返回任意类型的值，类似于C语言的void*类型。
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func (list *List) push(value interface{}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { node := new(List) node.push("abc") node.push(3.142) node.push('a') node.push(3 + 4i) node.push([]int{1, 2, 3}) node.push([8]byte{'a', 3: 'd'}) node.push(Node{1, &Node{2, nil}}.data) node.push(Node{1, &Node{2, nil}}.next) node.travel() } /*输出： abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 <nil>}<nil> */
实例01
把字串中汉字除外的所有字符逐个存入链表，且数字以整型保存。
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func (list *List) push(value interface{}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { node := new(List) str := "Golang数据结构123:单链表0789" for _, s := range str { if s >= 48 && s < 58 { node.push(s - 48) } else if s < 128 { node.push(string(s)) } } node.travel() } /*输出： G->o->l->a->n->g->1->2->3->:->0->7->8->9<nil> */
快慢指针
给单链表设置2个指针，其中一个指针先移动n个节点，然后同时移动这2个指针，那么当先移动的指针到达尾部时，后移动的那个指针就是倒数第 n 个节点。先移动的指针称“快指针”，后出发的指针称“慢指针”，其实一样“快”只是出发有先后。
实例02
删除链表中倒数第 n 个结点
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func (list *List) removNthBack(n int) { if n > list.size() { panic("range error: n <= List's size") } var fast, slow *Node head := list.head fast = head slow = head for i := 0; i < n; i++ { fast = fast.next } if fast == nil { list.head = head.next return } for fast.next != nil { fast = fast.next slow = slow.next } slow.next = slow.next.next } func removNthBack(list *List, n int) *List { if n > list.size() { panic("range error: n <= List's size") } var fast, slow *Node head := list.head fast = head slow = head for i := 0; i < n; i++ { fast = fast.next } if fast == nil { list.head = head.next return list } for fast.next != nil { fast = fast.next slow = slow.next } slow.next = slow.next.next return list } func (list *List) push(value interface{}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) size() int { length := 0 for p := list.head; p != nil; p = p.next { length++ } return length } func (list *List) travel() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { lst := new(List) str := "12309" for _, s := range str { lst.push(s - 48) } lst.travel() lst.removNthBack(3) lst.travel() lst = removNthBack(lst, 3) lst.travel() lst.removNthBack(2) lst.travel() //lst.removNthBack(10) //panic error lst.removNthBack(2) lst.travel() lst.removNthBack(1) lst.travel() //lst.removNthBack(1) //panic error } /*输出： 1->2->3->0->9<nil> 1->2->0->9<nil> 1->0->9<nil> 1->9<nil> 9<nil> <nil> */
反转链表
遍历一个链表，每个结点用头插法相接的新链表就是原链表的反转结果。
实例03
反转整个链表
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func (list *List) reverse() { res := &List{} for p := list.head; p != nil; p = p.next { node := &Node{p.data, nil} node.next = res.head res.head = node } list.head = res.head } func (list *List) pushHead(value interface{}) { node := &Node{data: value} node.next = list.head list.head = node } func (list *List) build(lst []interface{}) { for i := len(lst) - 1; i >= 0; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) clear() { list.head = nil } func (list *List) travel() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { lst := new(List) for n := 5; n > 0; n-- { lst.pushHead(n) } lst.travel() lst.reverse() lst.travel() lst.clear() lst.build([]interface{}{6.13, "/", 100000, "Hann", 1.0e-5}) lst.travel() lst.reverse() lst.travel() } /*输出： 1->2->3->4->5<nil> 5->4->3->2->1<nil> 6.13->/->100000->Hann->1e-05<nil> 1e-05->Hann->100000->/->6.13<nil> */
实例04
反转链表的其中一段，反转从第m个结点到n个结点(其中0<m<=n<=length of List)
Input: 1->2->3->4->5->nil, m = 2, n = 4
Output: 1->4->3->2->5->nil
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func reverseBetween(list *List, m int, n int) *List { list = list.Copy() head := list.head if head == nil || m >= n { return list } if m < 1 { //防止范围左端超限 m = 1 } node := &Node{0, head} p := node for i := 0; p.next != nil && i < m-1; i++ { p = p.next } if p.next == nil { return list } cur := p.next for i := 0; i < n-m && cur.next != nil; i++ { //由cur.next != nil防止范围右端超限 tmp := p.next p.next = cur.next cur.next = cur.next.next p.next.next = tmp } list.head = node.next return list } func (list *List) reverseBetween(m int, n int) { head := list.head if head == nil || m >= n { return } if m < 1 { //防止范围左端超限 m = 1 } node := &Node{0, head} p := node for i := 0; p.next != nil && i < m-1; i++ { p = p.next } if p.next == nil { return } cur := p.next for i := 0; i < n-m && cur.next != nil; i++ { //由cur.next != nil防止范围右端超限 tmp := p.next p.next = cur.next cur.next = cur.next.next p.next.next = tmp } list.head = node.next } func (list *List) pushHead(value interface{}) { node := &Node{data: value} node.next = list.head list.head = node } func (list *List) build(lst []interface{}) { 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() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { list1 := new(List) list2 := new(List) for n := 5; n > 0; n-- { list1.pushHead(n) } list1.travel() list2 = reverseBetween(list1, 2, 4) list2.travel() list2 = reverseBetween(list1, 2, 3) list2.travel() list2 = reverseBetween(list1, 2, 5) list2.travel() list2 = reverseBetween(list1, 2, 6) list2.travel() list2 = reverseBetween(list1, 1, 6) list2.travel() list2 = reverseBetween(list1, 0, 3) list2.travel() list1.reverseBetween(1, 3) list1.travel() } /*输出： 1->2->3->4->5<nil> 1->4->3->2->5<nil> 1->3->2->4->5<nil> 1->5->4->3->2<nil> 1->5->4->3->2<nil> 5->4->3->2->1<nil> 3->2->1->4->5<nil> 3->2->1->4->5<nil> */
交换节点
实例05
链表的相邻节点两两交换位置
Given 1->2->3->4, you should return the list as 2->1->4->3.
package main import "fmt" type Node struct { data interface{} next *Node } type List struct { head *Node } func (list *List) swapPairs() { p := list.head if p == nil || p.next == nil { return } head := p.next var node, node2 *Node for p.next != nil { cur := p.next if node != nil && node.next != nil { node.next = cur } if p.next.next != nil { node2 = p.next.next } if p.next.next != nil { p.next = node2 } else { p.next = nil } cur.next = p node = p if p.next != nil { p = node2 } } list.head = head } func swapPairs(list *List) *List { list = list.Copy() p := list.head if p == nil || p.next == nil { return list } head := p.next var node, node2 *Node for p.next != nil { cur := p.next if node != nil && node.next != nil { node.next = cur } if p.next.next != nil { node2 = p.next.next } if p.next.next != nil { p.next = node2 } else { p.next = nil } cur.next = p node = p if p.next != nil { p = node2 } } list.head = head return list } 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) build(lst []interface{}) { for i := len(lst) - 1; i >= 0; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt.Print(p.data) p = p.next if p != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { list1 := new(List) list2 := new(List) list1.build([]interface{}{1, 2, 3, 4, 5, 6}) list1.travel() list2 = swapPairs(list1) list2.travel() list2 = &List{&Node{0, nil}} list2.head.next = list1.Copy().head list2.travel() list2.swapPairs() list2.travel() } /*输出： 1->2->3->4->5->6<nil> 2->1->4->3->6->5<nil> 0->1->2->3->4->5->6<nil> 1->0->3->2->5->4->6<nil> */
