力扣
209移除链表
思路：
第一：
首先明白 链表中的元素是无法被真正的删除的 只能替换指针的指向的元素
第二：
这道题是说移除链表中的目标元素，需要创建一个虚拟节点dummy去始终指向我们的头节点，能够保证我们最后输出的时候是从头部到尾部 顺序是保持的。
第三：
如何删除？举个例子 [1，2，3]比如我们要删除的元素是2. 那么当我们指针指向1的时候，进行判断，如果当前元素指向的下一个元素是要删除的值，那么我们就改变这个元素的指向，变成指向下下个元素，也就是跳过了中间的元素2.这也就是我们的删除操作。
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_node = ListNode(0,head)
cur = dummy_node
while cur.next!=None:
if cur.next.val ==val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_node.next707 设计链表
题目不难 但是很多细节问题
思路：
这里面都有一个共同点，都会涉及到一个链表元素的下标。那就是说我们需要判断这个index是不是大于链表长度或者说这个index是负数。这是两种特殊情况。
第一：
我们需要额外创建一个listnode类，为了需要插入的节点做一个初始化。
第二：
需要判断，如果是添加节点到指定index的前一位，那么我们的循环就是for xx in range(index)这里循环刚好到指定index的上一位截止。然后创建我们的node。并且注意:这里我们需要一个临时变量来储存新元素
举个例子：
1->2->3->5，我要在5的前面插入一个4.那么我循环index到3的位置的时候就停下了，这时候创建节点4，首先让节点4指向5，其次再让当前的节点3指向4.所以这里需要一个temp_node来作为临时变量去存新元素。
代码：
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.head = ListNode(0)
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
cur = self.head
for i in range(index+1):
cur = cur.next
if cur==None:
return -1
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0,val)
def addAtTail(self, val: int) -> None:
new_node = ListNode(val)
pre = self.head
for _ in range(self.size+1):
while pre.next:
pre = pre.next
pre.next = new_node
self.size+=1
def addAtIndex(self, index: int, val: int) -> None:
if index>self.size:
return
if index<0:
index = 0
#获取隐藏的头节点
p = self.head
#遍历获取增加节点的上一个节点
for j in range(index):
p = p.next
#创建新节点 让虚拟头节点指向新节点
temp_node = ListNode(val)
#注意 要将被插入的节点指向原节点的下一个节点
temp_node.next = p.next
#将原节点指向被插入的新节点
p.next = temp_node
self.size+=1
def deleteAtIndex(self, index: int) -> None:
#判断index是否有效
if index<0 or index>=self.size:
return
#获取隐藏的头节点
p = self.head
#获取被删除节点的上一个节点
for j in range(index):
p = p.next
#告诉当前节点，下个节点位下下个节点
p.next = p.next.next
self.size-=1 206反转链表
力扣
还是看了carl哥书上写的思路
思路：
首先这里需要用到一个双指针，一个cur指向头部，一个pre指针赋值为none.
同时还需要一个temp指针来保存cur的下一个元素。
然后pre和cur指针不断交换，链表最后也反转完成，最后return pre指针就可以了。
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre代码：
