go语言｜数据结构：单链表（2）-阿里云开发者社区

单向链表

　　又称单链表，单链表中每个结点包含两部分，分别是数据域和指针域，上一个结点的指针指向下一结点，依次相连，形成链表。三个概念：首元结点、头结点和头指针，其中头结点在链表中不是必须的。

首元结点

就是链表中存储第一个元素的结点。

头结点

是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以存储链表的长度或者其它的信息，也可以为空不存储任何信息。

头指针

是指向链表中第一个结点的指针。若链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向首元结点。

链表与节点

引入单链表结构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>
*/