链表
今日任务
● 链表理论基础 ● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表
详细布置
链表理论基础
建议：了解一下链接基础，以及链表和数组的区别
文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
203.移除链表元素
建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。
题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
707.设计链表
建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点
题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
206.反转链表
建议先看我的视频讲解，视频讲解中对 反转链表需要注意的点讲的很清晰了，看完之后大家的疑惑基本都解决了。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
代码
结构
go
type ListNode struct{
val int
next *ListNode
}
java
public class listnode{
int val;
listnode next;
public listnode(){}
public listnode(int val){
this.val = val;
}
public listnode(int val,listnode next){
this.val = val;
this.next = next;
W}
}
移除链表元素
链接
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeElements(head *ListNode, val int) *ListNode {
temp := &ListNode{}
temp.Next = head
ans := temp
for i := head; i != nil; i = i.Next{
if i.Val == val{
temp.Next = i.Next
}else{
temp.Next = i
temp = temp.Next
}
}
return ans.Next
}
这边主要是我设定了一个temp作为pre节点，其实优化的话可以让temp来进行遍历，然后判断temp next的值
707.设计链表
建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点
题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
题目链接：https://leetcode.cn/problems/design-linked-list/
tm不写了
// 节点结构体
type Node struct {
Val int
Next *Node
}
// MylinkedList是一个对象，需要去实现LinkedList接口的所有方法
type MyLinkedList struct {
DummyHead *Node //虚拟头节点
Size int //链表长度
}
//创建一个链表
func Constructor() MyLinkedList { //成功
// 创建一个虚拟头节点，非真正的头节点(真正的头节点是数组第一个节点)
dummyHead := &Node{
Val : -1,
Next : nil,
}
return MyLinkedList{DummyHead: dummyHead,Size: 0}
}
// 获取index位置的元素Val
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
func (this *MyLinkedList) Get(index int) int {
// 判断index是否非法
if (index < 0) || (index > (this.Size - 1)) {
return -1
}
// 查找
var cur *Node = this.DummyHead// dummy节点的index = -1
for i := 0;i <= index;i++ {//找到index为 index的节点
cur = cur.Next //0,1,2,3,4....index
}
return cur.Val
}
// 在头节点前面再次添加一个节点
func (this *MyLinkedList) AddAtHead(val int) { //成功
// 在dummy节点后面直接添加一个节点
var newNode *Node = &Node{Val:val, Next:nil,} //所有变量都要显示的初始化
newNode.Next = this.DummyHead.Next
this.DummyHead.Next = newNode
this.Size++
}
// 在尾结点添加节点
func (this *MyLinkedList) AddAtTail(val int) {
var newNode *Node = &Node{val, nil}
cur := this.DummyHead
for cur.Next != nil { //找到末尾节点
cur = cur.Next
}
cur.Next = newNode //新元素添加到末尾节点后面
this.Size++
}
// 在index节点前面添加一个节点
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
}
var newNode *Node = &Node{val, nil}
cur := this.DummyHead
for i:=0; i<=index-1; i++ { //找到index为 index-1的节点,如果index=0，则不会进入循环，直接插入到dummy后面
cur = cur.Next
}
newNode.Next = cur.Next
cur.Next = newNode
this.Size++
}
// 删除index节点
func (this *MyLinkedList) DeleteAtIndex(index int) {
// 判断是否有效
if index > this.Size-1 || index < 0 {
return
}
cur := this.DummyHead
for i := 0; i <= index-1; i++ {
cur = cur.Next
}
cur.Next = cur.Next.Next
this.Size--
}
// func main(){
// obj := Constructor()
// obj.AddAtHead(1)
// obj.AddAtTail(2)
// obj.AddAtIndex(0,0)
// obj.DeleteAtIndex(0)
// fmt.Println(obj.Get(0),obj.Get(1),obj.Get(2))
// }
206.反转链表
建议先看我的视频讲解，视频讲解中对 反转链表需要注意的点讲的很清晰了，看完之后大家的疑惑基本都解决了。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
leetcode :https://leetcode.cn/problems/reverse-linked-list/
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newhead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newhead
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode = nil
cur := head
nex := head
for cur != nil{
nex = cur.Next
cur.Next = prev
prev = cur
cur = nex
}
return prev
}
