刷题笔记day03-链表

前言

今天是刷题的第三天，坚持就是胜利

203.移除链表元素

增加一个头结点，这样可以统一删除操作
另外，遇到等于的值，就让 prev 指向 curr.Next ，同时将curr更新指向 prev.Next。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func removeElements(head *ListNode, val int) *ListNode {// 思路：增加一个头结点，并且设置一个prev指针，用于删除newHead := &ListNode{}newHead.Next = headprev := newHeadcurr := newHeadfor curr != nil {if curr.Val == val {prev.Next = curr.Nextcurr = prev.Next} else {prev = currcurr = curr.Next}}return newHead.Next
}

707. 设计链表

测试代码，

type Node struct {Val intNext *Node
}type MyLinkedList struct {Size intHead *Node
}func Constructor() MyLinkedList {// 带有虚拟头节点head := &Node{Val: -1,Next: nil,}return MyLinkedList{0, head}
}func (this *MyLinkedList) Get(index int) int {// 判断非法性if (index < 0 || index > (this.Size - 1)) {return -1}node := this.Headfor i := 0; i <= index; i++ {if node == nil {return -1} else {node = node.Next}}return node.Val
}func (this *MyLinkedList) AddAtHead(val int)  {node := &Node {Val: val,Next: nil,}node.Next = this.Head.Nextthis.Head.Next = nodethis.Size++
}func (this *MyLinkedList) AddAtTail(val int)  {node := this.Head// node指向最后一位非nilfor node.Next != nil {node = node.Next}node.Next = &Node{Val: val,Next: nil,}this.Size++
}func (this *MyLinkedList) AddAtIndex(index int, val int)  {if index > this.Size {return }else if index == this.Size { //直接添加到末尾this.AddAtTail(val) return}else if index < 0 {index = 0}// header 指向插入位置的前一位header := this.Headfor i := 0; i <= index - 1; i++ {header = header.Next}node := &Node{val, nil}node.Next = header.Nextheader.Next = nodethis.Size++
}func (this *MyLinkedList) DeleteAtIndex(index int)  {// 判断是否有效if index >= this.Size || index < 0 {return}// header 指向插入位置的前一位header := this.Headfor i := 0; i <= index - 1; i++ {header = header.Next}header.Next = header.Next.Nextthis.Size--
}/*** Your MyLinkedList object will be instantiated and called as such:* obj := Constructor();* param_1 := obj.Get(index);* obj.AddAtHead(val);* obj.AddAtTail(val);* obj.AddAtIndex(index,val);* obj.DeleteAtIndex(index);*/

206. 反转链表

// 使用双指针，pre指向前一个，curr指向当前的，前后调转方向既可。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func reverseList(head *ListNode) *ListNode {// 使用双指针var prev *ListNodecurr := headvar tmp *ListNodefor curr != nil {tmp = curr.Nextcurr.Next = prevprev = curr// curr往后移动一位curr = tmp}return prev
}