leetcode力扣 707设计链表 go实现

记录一下leetcode刷题，大牛请绕道

代码

单链表

type Node struct {
	Val int // 存放数据
	Next *Node //指针指向下一个节点
}

//定义一个带头的单链表
type MyLinkedList struct {
	Head *Node
}

//初始化链表
func Constructor() MyLinkedList {
	head := &Node{Val: 0,Next: nil}
	return MyLinkedList{Head: head}
}

//获取链表的长度
func (this *MyLinkedList) Len() int {
	cur := this.Head
	count := 0
	for ; ; {
		if cur.Next != nil {
			count++
			cur = cur.Next
		} else {
			break
		}
	}
	return count
}

//获取链表中第 index 个节点的值。如果索引无效，则返回-1。
func (this *MyLinkedList) Get(index int) int {
	cur := this.Head.Next
	list_len := this.Len()
	if index >= list_len{
		return -1
	}else {
		for i := 0; i < index; i++ {
			cur = cur.Next
		}
		return cur.Val
	}
}

/*
在链表的第一个元素之前添加一个值为 val 的节点。
插入后，新节点将成为链表的第一个节点。
 */
func (this *MyLinkedList) AddAtHead(val int)  {
	//链表为空
	cur := this.Head
	node := &Node{Val: val}
	//如果只有虚拟头节点，那么直接把虚拟头节点的Next指向新插入的节点
	if cur.Next == nil{
		cur.Next = node
	}else {
		node.Next = cur.Next
		cur.Next = node
	}
}

//将值为 val 的节点追加到链表的最后一个元素。
func (this *MyLinkedList) AddAtTail(val int)  {
	cur := this.Head
	node := &Node{Val: val}
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = node
}

/*在链表中的第index个节点之前添加值为val 的节点。
如果index等于链表的长度，则该节点将附加到链表的末尾。
如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
*/
func (this *MyLinkedList) AddAtIndex(index int, val int)  {
	list_len := this.Len()
	node := &Node{Val: val}
	if index == list_len{
		this.AddAtTail(val)
	}else if index <= 0{
		this.AddAtHead(val)
	}else if index > list_len{
		//不插入
	}else {
		prev := this.GetNode(index -1)
		node.Next = prev.Next
		prev.Next = node
	}
}

//获取指定节点的指针
func (this *MyLinkedList) GetNode(index int) *Node {
	cur := this.Head.Next  //头指针指向下一个节点
	list_len := this.Len() //获取链表的长度
	if index >= list_len{
		return nil
	}else if index == -1{
		return this.Head
	} else {
		// 遍历获得指定的位置
		for i := 0; i < index; i++ {
			cur = cur.Next
		}
		return cur
	}
}

//如果索引 index 有效，则删除链表中的第 index 个节点。
func (this *MyLinkedList) DeleteAtIndex(index int)  {
	list_len := this.Len()
	if index < list_len{
		prev := this.GetNode(index - 1)
		prev.Next = prev.Next.Next
	}else if index == 0 && list_len == 1{
		this.Head.Next = nil
	}
}