golang单向链表删除元素
时间复杂度O(1)
思路：删除的接点可以变成上一个节点，而不是真正的删除之后再拼接
package main
import (
"errors"
"fmt"
)
type NodeList struct {
Val int
Next *NodeList
}
func (head *NodeList) delete(cur *NodeList) error {
if head == nil || cur == nil {
return errors.New("节点异常")
}
if cur == head {
cur.Next = nil
return nil
}
if cur.Next == nil {
// 找到待删除节点得前驱节点
perNode := head
for perNode.Next == cur {
perNode = perNode.Next
}
perNode.Next = nil
return nil
}
nextNode := cur.Next
cur.Val = nextNode.Val
cur.Next = nextNode.Next
return nil
}
func (head *NodeList) traverse() {
for head != nil {
fmt.Println(head.Val)
head = head.Next
}
}
func main() {
head := new(NodeList)
head.Val = 1
ln2 := new(NodeList)
ln2.Val = 2
ln3 := new(NodeList)
ln3.Val = 3
ln4 := new(NodeList)
ln4.Val = 4
ln5 := new(NodeList)
ln5.Val = 5
head.Next = ln2
ln2.Next = ln3
ln3.Next = ln4
ln4.Next = ln5
err := head.delete(ln2)
if err != nil {
panic(err)
}
head.traverse()
}
