【基础】leetcode 203 移除链表元素
核心思路：1）设置一个虚拟节点 2）如果下一个节点值等于val的话，就删除下一个节点，但是仍然要停留在当前节点上！继续判断新的下一个节点 3）下一个节点值不等于val才将当前节点过渡到下一个节点
还要多练习，做到毫不犹豫写出来的程度
# python3
# 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]:
# 虚拟节点
dummy_head = ListNode(0, head)
node = dummy_head
while node.next != None:
if node.next.val == val:
node.next = node.next.next # 删除下一个节点，while还在继续，继续判断新的下一个节点
else:
node = node.next
return dummy_head.next
// c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy_head = new ListNode(0, head); // 右边是新增加的虚拟头节点，左边是指向该节点的指针
ListNode* cur = dummy_head;
while (cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* tmp = cur->next; // 必须要用tmp承接过来，不然就找不到了
cur->next = cur->next->next;
delete tmp; // 注意delete的写法
}
else {
cur = cur->next;
}
}
head = dummy_head->next;
delete dummy_head; // 虚拟头节点也要清除干净
return head;
}
};
【基础】leetcode 203 移除链表元素
核心思路：主要是要会写节点及链表的初始化函数
一些优化思路：1）定义链表时，_head直接定义成虚拟头节点，就不用在具体函数中再起虚拟头了 2）add和del对节点的操作可以一行直接写出来，简洁一点 3）双向链表，类似虚拟头节点，可以再定义一个虚拟尾节点 4）支持从尾巴查找节点
todo：优化思路的c++版本
# python3 单向链表
class listNode:
def __init__(self, val=0, next=None):
# 定义节点初始化方法
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
# 定义链表初始化方法
self._head = listNode()
self._cnt = 0
def get(self, index: int) -> int:
cur = self._head
if index >= self._cnt: # 注意_cnt从1到size，而index从0到size-1
return -1
else:
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val) # 一开始忘了传val
def addAtTail(self, val: int) -> None:
self.addAtIndex(self._cnt, val)
def addAtIndex(self, index: int, val: int) -> None:
if index < 0:
index = 0
if index > self._cnt:
return None
new_node = listNode(val=val) # python初始化一个类不用new
dummy_head = listNode(next=self._head)
cur = dummy_head
for _ in range(index):
cur = cur.next
new_node.next = cur.next
cur.next = new_node
self._cnt += 1 # 注意更改head的同时，cnt不要忘了加减
self._head = dummy_head.next
def deleteAtIndex(self, index: int) -> None:
if index >= self._cnt or index < 0:
return None
dummy_head = listNode(next=self._head)
cur = dummy_head
for _ in range(index):
cur = cur.next
cur.next = cur.next.next
self._cnt -= 1
self._head = dummy_head.next
# 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)
【基础】leetcode 206 反转链表
核心思路：先翻再动+双指针
而且是先动pre再动cur
todo: c++版本
# python3
# 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]:
pre = None
cur = head
while cur != None:
tmp = cur.next # 暂存翻转后要丢的节点
cur.next = pre # 翻转
pre = cur # 先动pre，再动cur
cur = tmp
return pre
【复习】leetcode 704 二分查找
耗时3min，一次通过；不过回想思路还是费了点劲，有点不自信的感觉，比预想的慢
【复习】leetcode 27 移除元素
耗时3min，感觉同上
day3 语法积累
- python 初始化
dummy_head = ListNode(0, head) or dummy_head = ListNode(next=head)
- c++ 初始化
ListNode* dummy_head = new ListNode(0, head);
- python 不用自己清除节点，c++ 记得自己做清除操作，另外清除之前用一个指针承接过来，不然就找不到了
