注：详细代码到https://github.com/go-snail/arithmetic/tree/master/link下载。
链表操作是数据结构中基本的操作，下面用golang实现一下链表的基本操作，包括增、删、查以及单链表的反转操作。
package link
import (
"fmt"
"github.com/pkg/errors"
)
//链表结构
type ListNode struct {
data int
next *ListNode
}
//初始化链表头，下面的所有操作都是基于带头链表
func NewListNode() *ListNode {
return &ListNode{next: nil}
}
//获取链表的长度
func (l *ListNode)Length() int {
len :=0
for l.next != nil {
len++
l = l.next
}
return len
}
//插入节点
func (l *ListNode)InsertNode(d int) error {
newNode :=new(ListNode)
newNode.data = d
newNode.next = l.next
l.next = newNode
return nil
}
//删除节点
func (l *ListNode)DelNode(d int) {
if l == nil {
errors.New("Empty List!")
return
}
for l.next != nil {
if l.next.data == d {
l.next = l.next.next
//return 此处控制找到相同数据是否全部删除操作
}
l = l.next
}
}
//遍历链表
func (l *ListNode)ListNode() {
for l.next != nil {
fmt.Printf(" %d", l.next.data)
l = l.next
}
}
//基于位置删除元素
func (pHead *ListNode)DelNodeById(id int) {
i :=1
node := pHead.next
tmp := pHead
for node != nil {
if i == id {
tmp.next = node.next
}
i++
tmp = node
node = node.next
}
if i < id {
errors.New("The Len of the list is less!")
}
}
//获取链表第一个元素
func (l *ListNode)GetFirstNode() *ListNode {
return l.next
}
//递归单链反转
func ReverseList(pHead, node *ListNode) *ListNode {
if node.next == nil {
pHead.next = node
return node
}
n := ReverseList(pHead, node.next)
if n != nil {
n.next = node
node.next = nil
}
return node
}
链表反转操作
//遍历单链反转方法
func (pHead *ListNode)ReverseListV2() {
pReversedHead := pHead
var pNode = pHead.next
var pPrev *ListNode
for pNode != nil {
pNext := pNode.next
if pNext == nil {
pReversedHead.next = pNode
}
pNode.next = pPrev
pPrev = pNode
pNode = pNext
}
return
}
删除链表中倒数第X位置的节点
此外，删除链表倒数第X个节点，尤其对于单向链表来说，每次只能从链表头开始，这里想到一个小技巧（有更好的方法的可以留言哦～～），先计算链表的总长度M，利用删除第N个节点的函数DelNodeById删除第X=M-N+1节点。
func (l *ListNode)DelReverseNode(dint) {
len := l.Length()
l.DelNodeById(len-d+1)
}
网友评论