数据结构：单向链表

定义单链表结构体

定义了HeadNode头节点。

type SinglyLinkedList struct {
    HeadNode *Node
}

定义节点结构体

定义了No、Name属性字段，Next指针用于指下当前节点的下一个节点

type Node struct {
    No   int
    Name string
    Next *Node
}

从链表尾部添加

若头节点为空，则直接将头节点赋值为新生成节点。

反之，遍历找到Next指针为nil的节点，让当前节点的Next指针指向新生成的节点。

// Append 从尾部添加
func (list *SinglyLinkedList) Append(no int, name string) {
    node := &Node{No: no, Name: name}
    temp := list.HeadNode
    if temp == nil {
        list.HeadNode = node
        return
    }
    for temp.Next != nil {
        temp = temp.Next
    }
    temp.Next = node
}

从链表头部添加

将新生成的节点的Next指针指向当前链表的头节点，再将头节点赋值为新生成的节点。

// Add 从头部添加
func (list *SinglyLinkedList) Add(no int, name string) {
    node := &Node{No: no, Name: name}
    if list.HeadNode == nil {
        list.HeadNode = node
    } else {
        node.Next = list.HeadNode
        list.HeadNode = node
    }
}

按编号从小到大插入链表

若头节点编号大于新生成节点，则将新生成节点从头部加入。

反之，轮询，若当前节点的下一个节点为nil，或者当前节点的下一个节点的编号大于新生成节点的编号，跳出轮询，将新生成的节点的下一个节点赋值为当前节点的下一个节点，再将当前节点的下一个节点赋值为新生成的节点。这样就将节点插入到两个节点之间了。

func (list *SinglyLinkedList) Insert(no int, name string) {
    node := &Node{No: no, Name: name}
    temp := list.HeadNode
    if temp == nil {
        list.HeadNode = node
        return
    }
    if temp.No > no {
        node.Next = temp
        list.HeadNode = node
    } else {
        for temp.Next != nil {
            if temp.Next.No > no {
                break
            }
            temp = temp.Next
        }
        node.Next = temp.Next
        temp.Next = node

    }
}

更新指定编号节点的字段值

轮询遍历当前节点的编号是否等于指定编号，找到指定节点后更新。

func (list *SinglyLinkedList) Update(no int, name string) {
    if list.HeadNode == nil {
        return
    }

    temp := list.HeadNode
    for temp.No != no {
        temp = temp.Next
    }

    if temp != nil {
        temp.Name = name
    }
}

删除指定编号的节点

func (list *SinglyLinkedList) Delete(no int) {
    if list.HeadNode == nil {
        return
    }
    temp := list.HeadNode
    if temp.No == no {
        list.HeadNode = list.HeadNode.Next
        return
    }

    for temp.Next != nil {
        if temp.Next.No == no {
            break
        }
        temp = temp.Next
    }

    temp.Next = temp.Next.Next
}

查找倒数第 N 个节点

首先获取链表长度，与传入的N做差，从链表头偏移length-N个即是倒数第N个节点。如：链表长度为10，求倒数第7个节点，则偏移10-7个即3个节点为所求节点。

func (list *SinglyLinkedList) LastIndex(index int) *Node {
    if index <= 0 || list.Length() < index {
        return nil
    }

    temp := list.HeadNode
    for i := 0; i < list.Length()-index; i++ {
        temp = temp.Next
    }
    return temp
}

链表的反转

定义next临时变量指向原始链表头节点的下一个节点，每次轮询从头部加入新生成的链表，完成反转。

func (list *SinglyLinkedList) Reverse() *SinglyLinkedList {
    temp := list.HeadNode

    if temp == nil || temp.Next == nil {
        return list
    }

    reverseList := new(SinglyLinkedList)

    var next *Node

    for temp != nil {
        next = temp.Next
        temp.Next = reverseList.HeadNode
        reverseList.HeadNode = temp
        temp = next
    }
    return reverseList
}

倒序打印

可以利用Golang语言的defer特性，类似栈的先进后出完成。

或者可使用正序遍历并依此加入栈中，再依此从栈中弹出。

func (list *SinglyLinkedList) ReversePrint() {
    temp := list.HeadNode
    for temp != nil {
        defer func(no int, name string) {
            fmt.Println("No#", no, "Name#", name)
        }(temp.No, temp.Name)
        temp = temp.Next
    }
}

合并两个有序链表

轮询指定的一个链表temp2，在轮询中与另一个链表temp1的节点编号进行比较，找到temp1中当前节点的下一个节点的编号大于temp2节点的编号的节点，从temp1链表中取下该节点，并插入到temp2中。

func MergeTwoOrderLinkedList(first, second *SinglyLinkedList) *SinglyLinkedList {
    if first == nil {
        return second
    }
    if second == nil {
        return first
    }

    temp2 := second.HeadNode

    var next *Node

    for temp2 != nil {
        next = temp2.Next

        temp1 := first.HeadNode
        if temp1.No < temp2.No {
            for temp1.Next != nil {
                if temp1.Next.No > temp2.No {
                    break
                }
                temp1 = temp1.Next
            }
            temp2.Next = temp1.Next
            temp1.Next = temp2
        } else {
            temp2.Next = temp1
            first.HeadNode = temp2
        }
        temp2 = next
    }
    return first
}

测试代码

func main() {
    singlyLinkedList := &SinglyLinkedList{}
    singlyLinkedList.Insert(1, "111")
    //singlyLinkedList.Append(1, "sj")
    singlyLinkedList.Insert(3, "333")
    singlyLinkedList.Insert(2, "222")
    singlyLinkedList.Insert(5, "555")
    singlyLinkedList.Insert(4, "444")
    singlyLinkedList.Print()
    fmt.Println("链表长度#", singlyLinkedList.Length())
    fmt.Println("-------------")
    singlyLinkedList.ReversePrint()
    fmt.Println("-------------")

    fmt.Printf("LastIndex#%+v\n", singlyLinkedList.LastIndex(1))

    singlyLinkedList.Update(1, "111111111111")
    singlyLinkedList.Update(3, "333333333333")

    singlyLinkedList.Delete(5)
    singlyLinkedList.Delete(4)
    singlyLinkedList.Delete(1)

    singlyLinkedList.Print()
    fmt.Println("链表长度#", singlyLinkedList.Length())

    fmt.Println("-------------")

    singlyLinkedList.Add(6, "666")

    singlyLinkedList.Print()
    fmt.Println("链表长度#", singlyLinkedList.Length())

    fmt.Println("------Reverse Print-------")
    singlyLinkedList.Reverse().Print()


    fmt.Println("-------------")


    first := &SinglyLinkedList{}
    //first.Insert(1, "111")
    first.Insert(3, "333")
    first.Insert(5, "555")
    first.Insert(7, "777")
    first.Insert(9, "999")

    second := &SinglyLinkedList{}
    second.Insert(1, "111")
    second.Insert(2, "222")
    second.Insert(4, "444")
    second.Insert(6, "666")
    second.Insert(8, "888")

    MergeTwoOrderLinkedList(first, second).Print()
}