代码如下
type Node struct { //定义一个节点 ，包含一个数据变量一个指针
Val int
Next *Node
}
type MyLinkedList struct { //定义一个链表 ，链表里面有一个虚拟头节点，和大小
Dummayhead *Node
Size int
}
func Constructor() MyLinkedList { //初始化 ：创建一个虚拟头结点，指针域为空，数值域为-1 大小为 0
dummayhead := &Node{
Val : -1 ,
Next : nil ,
}
return MyLinkedList{Dummayhead:dummayhead,Size:0}
}
func (this *MyLinkedList) Get(index int) int { //返回索引对应的值，思路;首先判断索引合不合法
因为链表长度为size，所以链表节点对应的下标是从0 到size-1 ，如果超出这个范围则不合法
if index < 0 || index > this.Size-1 {
return -1
}
cur := this.Dummayhead //开始遍历，定义一个遍历指针指向虚拟头结点
for i := 0 ; i <= index ; i++ { //一直向后移动直到index处
cur = cur.Next
} //结束循环时，cur指向index节点
return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) { 在头部添加元素
var newnode *Node = &Node{ // 先定义一个节点
Val : val ,
Next : nil ,
}
newnode.Next = this.Dummayhead.Next //虚拟头结点的next指针赋值给新创建节点的next指针，目的是让新创建的指针指向原本链表的头节点，那么新创建的节点就会成为新的头结点
this.Dummayhead.Next = newnode //虚拟头节点在指向这个新创建的节点
this.Size++ //最后链表长度加1
}
func (this *MyLinkedList) AddAtTail(val int) { //在尾部添加一个节点
var newnode *Node = &Node{
Val : val ,
Next : nil ,
}
cur := this.Dummayhead //定义一个遍历指针
for cur.Next != nil { //只要该节点的下一个节点不为空，则一直向后遍历
cur = cur.Next
}
cur.Next = newnode
this.Size++
}
func (this *MyLinkedList) AddAtIndex(index int, val int) { //在index处添加一个节点
if index > this.Size { //判断index是否合法
return
}else if index == this.Size { //如果index等于size，则说明需要队尾添加一个元素，所以直接调用队尾添加元素函数
this.AddAtTail(val)
return
}else if index < 0 {
index = 0
}
cur := this.Dummayhead //定义一个遍历指针
for i := 0 ; i <= index-1 ; i++ { //这时候需要遍历到index前一个节点
cur = cur.Next
}
var newnode *Node = &Node { //定义一个节点
Val : val ,
Next : nil ,
}
newnode.Next = cur.Next //cur的next指针赋值给新定义节点的next指针
cur.Next = newnode //在将cur的next指针域指向新的节点
this.Size++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index > this.Size - 1 {
return
}
cur := this.Dummayhead
for i := 0 ; i <= index-1 ; i++ { //遍历到目标节点的前一个节点
cur = cur.Next
}
cur.Next = cur.Next.Next //直接将目标节点的下一个节点赋值给当前遍历到的节点的next指针域
this.Size--
}
206 翻转链表
代码如下 思路如下 ：设置两个指针
pre指针最开始指向空，cur指向头结点，然后将cur直接指向pre，在将cur向后移动，这样做之后，所有的节点都会指向自己的前一个节点，那么在前面的节点就会变为在后面的节点
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
24 两两交换链表中的节点
代码如下
注： 这题需要画图，我不知道如何用文字清晰的表达
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{
Next : head ,
}
pre := dummy
for head != nil && head.Next != nil {
tmp := head.Next.Next
pre.Next = head.Next
head.Next.Next = head
head.Next = tmp
pre = head
head = tmp
}
return dummy.Next
}
