链表基础理论:https://programmercarl.com/链表理论基础.html
203题目链接:https://leetcode.cn/problems/remove-linked-list-elements/
203代码随想录:https://programmercarl.com/0203.移除链表元素.html#算法公开课
707题目链接:
https://leetcode.cn/problems/design-linked-list/description/
707代码随想录:https://programmercarl.com/0707.设计链表.html#其他语言版本
206题目链接:https://leetcode.cn/problems/reverse-linked-list/submissions/535001438/
206代码随想录:
https://programmercarl.com/0206.翻转链表.html#其他语言版本
链表基础知识笔记
链表示意图
单链表(如上图)
class linknode:
def __init__(self,val,next = None):
self.val = val
self.next = next
双链表
class blinknode:
def __init__(self,val,next = None,front = None):
self.val = val
self.next = next
self.front = front
链表操作
删除节点
加入节点
203.移除链表元素
重点内容
- 设置虚拟头节点,在删除头节点时会更便利;
- 考虑链表遍历的条件和范围
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
node_1 = ListNode()
node_1.next = head
curr = node_1
while curr.next:
if curr.next:
if curr.next.val == val:
curr.next = curr.next.next
continue
curr = curr.next
return node_1.next
707 设计链表
重点内容:
- 基本可以自己复现
- 问题1:可以设置self.size 遍历循环
- 遍历到index前一个和index当前那一个的公式不同
- get 和 delete的范围[0,size) add——index范围是[0,index]
curr = self.dummy_node
for i in range(curr):
curr = curr.next
### 结束时 curr为index的前一个
最终解答:
class Node:
def __init__(self,val=0 ,next = None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.headnode = Node()
self.size = 0
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
curr = self.headnode.next
for i in range(index):
curr = curr.next
return curr.val
def addAtHead(self, val: int) -> None:
node_1 = Node(val)
node_1.next = self.headnode.next
self.headnode.next = node_1
self.size = self.size+1
def addAtTail(self, val: int) -> None:
node_1 = Node(val)
curr = self.headnode
while curr.next:
curr = curr.next
curr.next = node_1
self.size = self.size+1
def addAtIndex(self, index: int, val: int) -> None:
if index<0 or index>self.size:
return
node_1 = Node(val)
curr = self.headnode
for i in range(index):
curr = curr.next
node_1.next = curr.next
curr.next = node_1
self.size =self.size+1
def deleteAtIndex(self, index: int) -> None:
if index>=0 and index<self.size:
curr = self.headnode
for i in range(index):
curr = curr.next
curr.next = curr.next.next
self.size = self.size-1
else:
return
206反转链表
重点:
- 第一遍没做出来,但其实只要想起来双指针就会了;
- python的迭代和递归区别不太大
最终解答:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
pre = None
while curr:
tmp = curr.next
curr.next = pre
pre = curr
curr = tmp
return pre
标签:node,index,203,curr,val,206,self,随想录,next
From: https://www.cnblogs.com/P201821440041/p/18214549