链表理论基础
文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
注意一下链表在java中的代码实现，学校居然不讲这个。
203.移除链表元素
建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。
题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
虚拟头节点：为了避免单独处理head被删除的情况
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// If the head is null, return null
if (head == null) {
return null;
}
// Create a dummy node that points to the head
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
// Traverse the list
while (cur != null) {
// If current node's value equals the target value, remove it
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
// Move to the next node regardless of whether cur was deleted
cur = cur.next;
}
// Return dummy.next instead of head to handle cases where head is deleted
return dummy.next;
}
}
- 自己写的过程中出现的问题
cur = cur.next;写入了if条件语句内部，没有考虑到当cur.val != val的情况下，cur 并不会移动，要保证向后走。
707.设计链表
题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
单链表
// Single linked list node class
class LinkNode {
int val; // Value of the node
LinkNode next; // Pointer to the next node
public LinkNode() {}
public LinkNode(int val) {
this.val = val;
}
}
class MyLinkedList {
int size; // Length of the linked list
LinkNode head; // Dummy head node
// Initialize the linked list
public MyLinkedList() {
size = 0;
head = new LinkNode(0); // Dummy head node with value 0
}
// Get the value of the index-th node
public int get(int index) {
// Check if the index is valid
if (index < 0 || index >= size) {
return -1;
}
LinkNode currentNode = head;
// Traverse to the index-th node
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
// Add a node at the head
public void addAtHead(int val) {
addAtIndex(0, val);
}
// Add a node at the tail
public void addAtTail(int val) {
addAtIndex(size, val);
}
// Add a node before the index-th node
public void addAtIndex(int index, int val) {
// If index is greater than the length of the list, do not insert the node
if (index > size) {
return;
}
// If index is less than 0, insert the node at the head
if (index < 0) {
index = 0;
}
size++;
LinkNode pre = head; // Create a predecessor node
// Traverse to the node before the index-th node
for (int i = 0; i < index; i++) {
pre = pre.next;
}
LinkNode addNode = new LinkNode(val);
addNode.next = pre.next;
pre.next = addNode;
}
// Delete the index-th node
public void deleteAtIndex(int index) {
// Check if the index is valid
if (index < 0 || index >= size) {
return;
}
size--;
LinkNode pre = head; // Create a predecessor node
// Traverse to the node before the index-th node
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
}
}
-
自己写错的地方：
get()的if条件判断中
// i <= index是因为有虚拟头节点 for(int i = 0; i <= index; i++){
一开始写成了i < indexdeleteAtIndex中if条件判断一开始写的是index > size,忽略到当index=size时也越界了。
双链表
// 双链表
// 1. 定义链表节点类
class LinkNode{
int val;
LinkNode next, prev;
public LinkNode(){}
public LinkNode(int val){
this.val = val;
}
}
// 2. 定义链表类
class MyLinkedList {
int size; //链表中元素的数量
LinkNode head, tail; //虚拟头节点和尾节点
public MyLinkedList() {
this.size = 0;
this.head = new LinkNode(0);
this.tail = new LinkNode(0);
head.next = tail;
tail.prev = head;
}
// 实现get方法获取节点值
public int get(int index) {
if(index < 0 || index >= size){
return -1;
}
LinkNode currentNode;
// 判断哪一边历时更短
if(index >= size/2){
currentNode = tail;
for(int i = size; i > index; i--){
currentNode = currentNode.prev;
}
}else{
currentNode = head;
for(int i = 0; i <= index; i++){
currentNode = currentNode.next;
}
}
return currentNode.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index < 0){
index = 0;
}
size++;
LinkNode pre = head;
for(int i = 0; i < index; i++){
pre = pre.next;
}
// 新建结点
LinkNode addNode = new LinkNode(val);
addNode.next = pre.next;
pre.next.prev = addNode;
addNode.prev = pre;
pre.next = addNode;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
size--;
LinkNode pre = head;
for(int i = 0; i < index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
问题：
依然是get方法中的if条件判断，一开始没有意识到用双链表的话，两个区间应该能接上才对
if(index >= size/2){
currentNode = tail;
for(int i = size; i > index; i--){
currentNode = currentNode.prev;
}
}else{
currentNode = head;
for(int i = 0; i <= index; i++){
currentNode = currentNode.next;
}
}
看了视频的记录：
- 获取第n个节点中对n进行赋值，还有对while中怎么操作，想清楚极端情况即可：如果链表里返回第0个节点的结果，看有没有空指针异常或者指向错误。
- 头部插入节点的坑：正确的顺序应该是先连接后面的边，让插入的节点指向 pre.next；然后再添加前面的边pre.next = addNode;
- 尾部插入节点：current = dummy head，想象极端情况，应该让current指向尾部，current.next=null停止while循环
- 第n个节点前插入节点：要知道index的前节点才能插入。所以current指向index的前一个节点。
while(n--){
//想象极端情况，比如第0个节点，所以第0个节点应该是current.next
//所以current.next 是第n个节点
}
删除第n个节点：current=dummy head。要删第n个节点，还是要知道前一个节点的指针。所以第n个节点一定是current.next。
总结：
虚拟头结点。
current.next 才是第n个点。
先更新后面的边，再更新前面。
感觉视频更清晰些，可以跟着视频的思路自己再实现一遍。
206.反转链表
题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while(cur != null){
temp = cur.next; // Save the next node
cur.next = pre; // Current node points to the previous node
pre = cur; // Move the previous pointer
cur = temp; // Move the current pointer
}
return pre;
}
}
只实现了双指针法，递归等二刷再做。
看了视频，注意几个边界条件：
先移动pre，后移动current。
最后current指向null，pre就指向新列表的头结点。所以返回pre。
以后应该直接上手写一遍，不能反复看题解，否则一直看了忘忘了看……
