【代码随想录】算法训练计划03
1、203. 移除链表元素
题目:
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
思路:
- 移除链表元素,链表一定要注意虚拟头
- 不要忘记不删除的时候要前移元素
- 注意 cur 的赋值方式
- 注意是初始化一个虚拟头节点,和声明分别开
// 代码一刷——虚拟头
func removeElements(head *ListNode, val int) *ListNode {
dummy := &ListNode{}
dummy.Next = head
//cul.Next := head 这种写法错了
cul := dummy
for cul.Next != nil {
if cul.Next.Val == val {
cul.Next = cul.Next.Next
} else { // 不要忘记前移
cul = cul.Next
}
}
return dummy.Next
}
2、707. 设计链表
题目:
题目太长了就不复制了
思路:
- 这题吧,主要两点
- 1、注意条件说的是 index 是下标
- 2、注意边界条件,-1 啥的
// 代码一刷
type SingleNode struct {
Val int
Next *SingleNode
}
type MyLinkedList struct {
dummyHead *SingleNode
Size int
}
func Constructor() MyLinkedList {
newNode := &SingleNode{
-99,
nil,
}
return MyLinkedList{
dummyHead: newNode,
Size: 0,
}
}
func (this *MyLinkedList) Get(index int) int {
//获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1
if this == nil || index < 0 || index >= this.Size {
return -1
}
cur := this.dummyHead.Next
for i:=0; i<index; i++ {
cur = cur.Next
}
return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
newNode := &SingleNode{Val:val}
newNode.Next = this.dummyHead.Next
this.dummyHead.Next = newNode
//return this.Next
this.Size++
}
func (this *MyLinkedList) AddAtTail(val int) {
cur := this.dummyHead
for cur.Next != nil {
cur = cur.Next
}
newNode := &SingleNode{Val: val}
cur.Next = newNode
this.Size++
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
//
if index < 0 {
index = 0
} else if index > this.Size {
return
}
newNode := &SingleNode{Val:val}
cur := this.dummyHead
for i:=0; i<index; i++ {
cur = cur.Next
}
newNode.Next = cur.Next
cur.Next = newNode
this.Size++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.Size {
return
}
cur := this.dummyHead
for i:=0; i<index; i++ {
cur = cur.Next
}
if cur.Next != nil {
cur.Next = cur.Next.Next
}
this.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);
*/
3、206. 反转链表
题目:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
思路:
- 写老多遍了,这最少是第 7 遍,说说这次注意点吧
- 1、注意声明两个变量,pre,cur
- 2、注意 pre 声明,但是不初始化,因为不要 nil,看输入输出就知道了
// 代码一刷——只需要声明一个 pre 即可,不需要初始化
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}