package main

import "fmt"

//单链的数据结构
type Node struct {
    value int
    next  *Node
}

type List struct {
    head *Node
}

//添加成有序的链表
//1.如果是空链表则插入链表第一个元素
//2.升序插入链表中，插入的值和已有的链表值作比较
func (l *List) AddValue(value int) {
    if l.head == nil {
        node := Node{value: value}
        l.head = &node
        return
    }
    item := l.head
    for ; item.next != nil; item = item.next {
        if item.value == value {
            return
        }
        //把插入的值和已有有序链表作比较，找到位置后，原有结点位置上的数据域变成新值，然后指向原有节点数据域生成的新节点
        if item.value > value {

            tmpValue := item.value
            node := Node{value: tmpValue, next: item.next}
            item.value = value
            item.next = &node
            return
        }
    }
    //处理最后的一个链表连接
    if item.value == value {
        return
    }
    node := Node{value: value}
    item.next = &node
}

//删除链表节点的数据
func (l *List) deleteLink(value int) {
    if l.head == nil {
        return
    }
    item := l.head
    for ; item.next != nil; item = item.next {
        //遍历链表元素，通过与value的值比较找到要删除的非尾部结点
        if item.value == value {
            item.value = item.next.value
            item.next = item.next.next
            break
        }
        //如果删除的是尾部结点
        if item.next.value == value && item.next.next == nil {
            item.next = nil
            break
        }
    }
}

//翻转单链
func (l *List) reserveLink(n *Node) {
    //如果链表为空，或者链表只有一个结点则返回
    if n == nil || n.next == nil {
        return
    }
    var prev *Node
    current := n
    //fmt.Printf("%v", current)
    //首先判断链表是否为空或只有一个节点，如果是，则直接返回不进行翻转。
    //如果不是，则定义prev和current两个指针，分别指向链表的前一个节点和当前节点。
    //在循环中，首先保存当前节点的下一个节点，将当前节点指向前一个节点，然后将指针向后移动。最后，将链表头指向翻转后的最后一个节点prev
    for current != nil {
        next := current.next
        current.next = prev
        //fmt.Printf("%v \n", current.value)
        prev = current
        current = next

    }
    l.head = prev
}

//循环打印链表的每个值
func (l *List) printLink() {
    item := l.head
    if item != nil {
        for ; item.next != nil; item = item.next {
            fmt.Printf("next value %d \n", item.value)
        }
        fmt.Printf("end value %d \n", item.value)
    }
}

func NewOneLink() *List {
    return &List{head: nil}
}

func main() {
    nLink := NewOneLink()
    nLink.AddValue(1)
    nLink.AddValue(4)
    nLink.AddValue(5)
    nLink.AddValue(9)
    nLink.AddValue(9)
    nLink.AddValue(9)
    nLink.AddValue(2)

    nLink.printLink()
    fmt.Println("下面是删除节点之后----------------------")
    //删除某个节点数据
    nLink.deleteLink(9)
    nLink.printLink()

    //翻转单链
    nLink.reserveLink(nLink.head)
    fmt.Println("打印翻转之后----------------------")
    //打印
    nLink.printLink()
}