package test32_deletenode

import (
    "fmt"
    "testing"
)

//go test -v -test.run TestDeleteNode
func TestDeleteNode(t *testing.T) {
    if true {
        head := &ListNode{}
        head.Val = 1

        head.Next = &ListNode{}
        head.Next.Val = 5

        head.Next.Next = &ListNode{}
        head.Next.Next.Val = 1

        head.Next.Next.Next = &ListNode{}
        head.Next.Next.Next.Val = 9

        headtemp := head
        for headtemp != nil {
            fmt.Print(headtemp.Val, "\t")
            headtemp = headtemp.Next
        }
        fmt.Println("删除前")
        head = DeleteNode1(head, 1)
        headtemp = head
        for headtemp != nil {
            fmt.Print(headtemp.Val, "\t")
            headtemp = headtemp.Next
        }
        fmt.Println("删除后，新增虚拟头")
    }
    if true {
        head := &ListNode{}
        head.Val = 1

        head.Next = &ListNode{}
        head.Next.Val = 5

        head.Next.Next = &ListNode{}
        head.Next.Next.Val = 1

        head.Next.Next.Next = &ListNode{}
        head.Next.Next.Next.Val = 9

        headtemp := head
        for headtemp != nil {
            fmt.Print(headtemp.Val, "\t")
            headtemp = headtemp.Next
        }
        fmt.Println("删除前")
        head = DeleteNode2(head, 1)
        headtemp = head
        for headtemp != nil {
            fmt.Print(headtemp.Val, "\t")
            headtemp = headtemp.Next
        }
        fmt.Println("删除后，换头法")
    }
}

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

//新增虚拟头，返回head.Next
func DeleteNode1(head *ListNode, val int) *ListNode {
    //前一个节点
    pre := &ListNode{}
    pre.Next = head
    //当前节点
    cur := head
    //头节点
    head = pre

    for cur != nil {
        if cur.Val == val { //如果当前节点正好是删除节点
            pre.Next = cur.Next //前一个节点指向后一个节点
        } else {
            pre = cur //不删除，需要遍历。当前节点变成前一个节点
        }
        //下一个节点变成当前节点
        cur = cur.Next
    }

    return head.Next
}

//换头，返回head
func DeleteNode2(head *ListNode, val int) *ListNode {
    //换头
    for head != nil && head.Val == val {
        head = head.Next
    }

    //当前节点
    cur := head
    //前一个节点
    var pre *ListNode = nil
    for cur != nil {
        if cur.Val == val { //如果当前节点正好是删除节点
            pre.Next = cur.Next //前一个节点指向后一个节点，pre节点不可能为空的
        } else {
            pre = cur //不删除，需要遍历。当前节点变成前一个节点
        }
        //下一个节点变成当前节点
        cur = cur.Next
    }

    return head
}