题目简介
203.移除链表元素 https://leetcode.cn/problems/remove-linked-list-elements/description/
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
707 https://leetcode.cn/problems/design-linked-list/description/
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 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 的节点。
206 https://leetcode.cn/problems/reverse-linked-list/description/
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
初见思路
203: 链表题一定通过next进行遍历，链表删除可以通过调整next指针达成，pre.next = cur.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if not head:
return head
# filter unwanted heads
while head and head.val == val:
head = head.next
dummy_head = ListNode(-1,head)
pre_node = dummy_head
cur_node = dummy_head.next
while cur_node:
if cur_node.val == val:
pre_node.next = cur_node.next
cur_node = pre_node.next
else:
cur_node = cur_node.next
pre_node = pre_node.next
return dummy_head.next
遍历处理前先遍历过滤一遍符合目标值切重复的节点，对于需要pre，cur，next三个节点的链表题，一定记得想在链表头增加一个dummy节点，配合方法更方便。另外这题其实也类似双指针滑动窗口，只不过记得窗口值一直为2。一开始做题卡住，就是因为忘记了dummy头节点的使用。
707: 在开始做该题时要注意一点，LeetCode 平台已经内置 ListNode 单链表节点类，可以直接使用，当然不知道这一点也可以马上自己实现一个很简单：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
本题的核心是addAtIndex方法，注意加在开头和结尾的两个方法都可以调用这个方法进行复用。
class MyLinkedList:
def __init__(self):
self.dummy = ListNode()
self.cnt = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.cnt:
return -1
cur = self.dummy.next
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.cnt, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
pre.next = ListNode(val, pre.next)
self.cnt += 1
def deleteAtIndex(self, index: int) -> None:
if index >= self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
cur = pre.next
pre.next = cur.next
cur.next = None # 清空值
self.cnt -= 1
同样，这道题的核心也是dummy头的使用。pre.next定位到当前节点位置，增加：pre.next = ListNode(val,pre.next)；删除pre.next = cur.next 是两个固定的的写法，各类链表题都通用。
206: 反转链表，非常经典的题目了，这题反而不需要设置一个dummy节点来进行交换， 需要把刚开始的pre节点设置为空，然后遍历，不断交换反转即可
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
pre, cur = None, head
while cur:
next_node = cur.next
cur.next = pre
pre = cur
cur = next_node
return pre
这个反转逻辑一开始不太直观，但是仔细思考理解：存下一节点信息，当前节点的下一个节点设为前一节点，前一节点往后顺延，指向当前节点，当前节点变为下一节点，完成翻转，就那么简单。
复盘思路
203:
https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.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
重点难点
链表的难点在于指针指向的元素的变换，捋清指针指向的元素位置很重要。
今日收获
学习了链表的构造和基本操作。
