代码随想录算法训练营第3天|链表理论基础、203. 移除链表元素、 707.设计链表、 206.反转链表

链表理论基础

❤️链表增删的时间复杂度都是$O(1)$，适合动态增删；查询时间复杂度$O(N)$不适合查询
🧡链表在内存中离散分布

做题的方法总结：

1️⃣ 虚拟头结点：链表的结构就决定了要想操作某一节点就要知道前面的一个节点，但是头结点是没有前一个节点的，如果不想特殊化处理头节点，可以引入一个虚拟头节点，目的是让头节点也变成一般节点
2️⃣创建的cur指针指向要被操作的节点的前一个节点
3️⃣插入新节点时：要先连接后一个节点，再断开前一个节点
4️⃣改变某一个节点的指向时：要先使用temp指针保存该节点的下一节点，否则会造成后续节点丢失

203. 移除链表元素

题目链接：link

1、题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

2、思路

链表移除某一个节点只需要将上一个节点的next指针指向下一个节点就行了

但是如果要移除头节点，头结点可是没有上一个节点的，所以要把头节点直接指向头节点的下一节点。

所以就要把所有节点分成两种情况：是头节点和不是头结点

但是也可以用一种情况来实现删除操作：加入虚拟头结点 ，这样头结点也变成了一般节点。

3、code

class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 使用虚拟头结点dummyhead = ListNode(-1) # 首先初始化虚拟头结点dummyhead.next = head # 让虚拟头结点的next指针指向头节点，这样就把头节点的处理变成了一般节点的处理cur = dummyhead # 令cur表示要删除的节点的前一个节点while cur.next != None:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummyhead.next 

❤️使用dummyhead保持在链表的最开始不动，cur来移动删除节点，最后返回dummyhead.next
💜 为啥不使用head？因为haed的值可能等于val，也会被删除

4、复杂度分析

1️⃣ 时间复杂度：$O(N)$
2️⃣ 空间复杂度：$O(1)$

707. 设计链表

题目链接：link

1、题目描述

实现 MyLinkedList 类：
MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

2、思路

1️⃣ 插入节点：先连接后面的节点，再连接前面的节点
2️⃣删除节点：指针要指向被删除节点的前一个节点

3、code

class LinkNode:def __init__(self,val,next):self.val = valself.next = Noneclass MyLinkedList:def __init__(self):self.dummyhead = LinkNode(-1,None)self.size = 0# def print(self):#     cur = self.dummyhead#     for i in range(self.size):#         print(cur.next.val)#         cur = cur.nextdef get(self, index: int) -> int:if index >= self.size:return -1# 如果链表是1,2,3，返回index = 1，就是2cur = self.dummyhead.nextfor i in range(0,index):cur = cur.nextreturn cur.valdef addAtHead(self, val: int) -> None:new_node = LinkNode(val,None)new_node.next = self.dummyhead.nextself.dummyhead.next = new_nodeself.size += 1returndef addAtTail(self, val: int) -> None:self.addAtIndex(self.size,val)returndef addAtIndex(self, index: int, val: int) -> None:if index > self.size:return# 原来是1,3，加入index = 1cur = self.dummyheadfor i in range(index):cur = cur.nextnew_node = LinkNode(val,None)new_node.next = cur.nextcur.next = new_nodeself.size += 1returndef deleteAtIndex(self, index: int) -> None:if index >= self.size:return# 链表是1,2,3，删除index = 1，链表变成1,3cur = self.dummyheadfor i in range(index):cur = cur.nextcur.next = cur.next.nextself.size -= 1return# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

206. 反转链表

题目链接：link

1、题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

2、思路

双指针

3、code

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:# 双指针方法# 首先初始化双指针cur = head # 先保存头结点pre = None # 因为头节点的反转下一个节点就是空节点 # 之后就是一节一节的反转链表，直到cur指向Nullwhile cur != None:temp = cur.next # 如果反转链表的next指向的话，会使得正向的指针消失，所以要先保存一下    cur.next = pre # 反转pre = cur # 要先后移precur = temp # 后移动curreturn pre

4、复杂度分析

1️⃣ 时间复杂度：$O(N)$
2️⃣ 空间复杂度：$O(1)$