LeetCode203：力扣
移除链表元素: 为了将处理头结点的逻辑和处理其他节点逻辑保持一致，引入了dummyHead
package algor.trainingcamp;
import algor.junior_algor.list.ListNode;
/**
* @author lizhe
* @version 1.0
* @description: https://leetcode.cn/problems/remove-linked-list-elements/
* @date 2023/4/7 12:31
* <p>
* 给你一个链表的头节点 head 和一个整数 val ，
* 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
* <p>
* 为什么要添加虚拟节点： 操作其他节点时，依赖的是头结点，为了将操作头结点和操作其他节点的逻辑保持一致，
* 因此设计成头结点后移的操作
*/
public class LeetCode203 {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
/**
* 设置前后两个节点
*/
ListNode pre = dummy;
ListNode cur = head;
/**
* 如果发现cur的值等于val 需要移除 => pre.next = cur.next
* 否则 pre 后移
*/
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
return dummy.next;
}
}
LeetCode707: 力扣
设计链表（基础中的基础，包含了删除，新增，查找等基础操作，还是会多做几遍）
package algor.trainingcamp;
/**
* @author lizhe
* @version 1.0
* @description: TODO
*
* 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val和next。val是当前节点的值，next是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性prev以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
*
* 在链表类中实现这些功能：
*
* get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。
* addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。
* addAtTail(val)：将值为val 的节点追加到链表的最后一个元素。
* addAtIndex(index,val)：在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
* deleteAtIndex(index)：如果索引index 有效，则删除链表中的第 index 个节点。
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/design-linked-list
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* 注: 添加节点时候 为什么是先 insertNode.next = pre.next; 再 pre.next = insertNode;？
*/
public class LeetCode707 {
}
/**
* 构建链表
*/
class MyLinkedList {
int size;
Node dummyHead;
public MyLinkedList() {
size = 0;
dummyHead = new Node(-1);
}
public int get(int index) {
if(index < 0 || index >= size){
return -1;
}
Node cur = dummyHead;
for(int i = 0;i <=index;i++){
cur = cur.next;
}
return cur.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++;
Node pre = dummyHead;
//找到待添加节点的位置
for(int i = 0;i < index;i++){
pre = pre.next;
}
Node insertNode = new Node(val);
insertNode.next = pre.next;
pre.next = insertNode;
}
/**
* 删除节点: 找到待删除节点的前一个节点 然后进行删除
* pre.next = pre.next.next
*/
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
Node pre = dummyHead;
for(int i = 0;i < index;i++){
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
}
class Node {
int val;
Node next;
public Node(int val){
this.val = val;
}
}
LeetCode206: 力扣
链表翻转:
cur.next = pre => pre = cur =>cur = next(原来的cur的后一个节点,提前存储) return pre;
package algor.trainingcamp;
import algor.junior_algor.list.ListNode;
/**
* @author lizhe
* @version 1.0
* @description: 反转链表
* 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
* @date 2023/4/7 12:44
*/
public class LeetCode206 {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp;
while(cur != null){
//保存cur原来的下一个节点 用来进行后续的节点后移
tmp = cur.next;
//节点翻转
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
