链表（Linked List） 是一种线性数据结构，它由一系列节点（Node）组成，每个节点包含两部分：

1. 数据域：存储数据元素。
2. 指针域：存储指向下一个节点的引用（或者是指针）。

链表的节点通过指针连接在一起，形成一条链状结构。链表的结构与数组不同，数组的内存是连续分配的，而链表中的节点可以分散在内存的不同位置，通过指针连接起来。

链表的类型

1. 单向链表（Singly Linked List）：

   • 每个节点只包含指向下一个节点的指针。
   • 访问时只能从头节点开始，按顺序遍历到目标节点。
   • 最后一个节点的指针指向 null，表示链表的结束。

     [数据 | 指针] -> [数据 | 指针] -> [数据 | 指针] -> null
     

2. 双向链表（Doubly Linked List）：

   • 每个节点包含两个指针，分别指向前一个节点和后一个节点。
   • 可以从任意节点双向遍历链表。

     null <- [数据 | 前指针 | 后指针] <-> [数据 | 前指针 | 后指针] <-> [数据 | 前指针 | 后指针] -> null
     

3. 循环链表（Circular Linked List）：

   • 在循环链表中，最后一个节点指向链表的第一个节点，而不是 null，使得链表形成一个循环结构。

     [数据 | 指针] -> [数据 | 指针] -> [数据 | 指针] -> (回到第一个节点)
     

链表的特点

• 动态大小：链表的大小可以动态调整，不像数组那样需要预定义大小。
• 插入和删除效率高：在链表中插入和删除元素的效率很高，尤其是在头部和中间插入/删除时，不需要像数组那样进行大量元素的移动。
• 随机访问性能较差：链表不支持直接访问任意元素，必须从头开始按顺序遍历，直到找到目标节点。

链表的优缺点

优点：

• 动态扩展：不需要固定大小，插入和删除操作简单。
• 节省空间：比数组更加节省空间，因为数组需要预留未使用的空间。

缺点：

• 访问效率较低：无法通过下标随机访问，必须遍历链表。
• 额外空间：每个节点都需要额外的指针来维护链接。

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

本题主要是将链表中数据元素等于val的元素进行“删除”，就是将此元素的上一个节点的指针指向此元素下一个节点的指针，从而跳过此元素实现删除，实质此元素或节点还在内存中。

我们采用定义一个虚拟头节点，让虚拟头节点指向head节点，再定义一个cur指针等于虚拟头节点，我们去用cur指针去遍历和删除数值等于val的节点，用while条件为cur.next不为空，然后判断cur.next.val是否等于val，如果等于就跳过此节点指向下一个节点，如果不等于就让cur = cur.next。最后返回虚拟头节点的下一个节点，，为什么不返回head呢，因为head在一开始判断其值时很有可能被删除掉了。

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int val=0, ListNode next=null) {*         this.val = val;*         this.next = next;*     }* }*/
public class Solution {public ListNode RemoveElements(ListNode head, int val) {ListNode dummy = new ListNode();dummy.next = head;ListNode cur = dummy;while(cur.next!=null){if(cur.next.val==val){cur.next = cur.next.next;}else{cur = cur.next;}}return dummy.next;}
}

707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

• 0 <= index, val <= 1000
• 请不要使用内置的 LinkedList 库。
• 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

• Get(int index) 方法:

  • 通过索引获取对应节点的值，首先检查索引是否在合法范围内，然后从虚拟头节点开始遍历链表，直到到达目标节点，返回节点值。

• AddAtHead(int val) 方法:

  • 在链表头部插入新节点，将新节点的 next 指向当前链表的第一个有效节点，并更新 size。

• AddAtTail(int val) 方法:

  • 在链表尾部插入新节点，从虚拟头节点开始遍历，找到最后一个节点后，将其 next 指向新节点，更新 size。

• AddAtIndex(int index, int val) 方法:

  • 检查索引是否有效，遍历链表到达指定位置，插入新节点，并正确调整相邻节点的 next 引用，更新 size。

• DeleteAtIndex(int index) 方法:

  • 首先检查索引是否在合法范围内，遍历链表到达要删除节点的前一个节点，调整其 next 引用，跳过要删除的节点，更新 size。

public class NodeList{public int val;public NodeList next;public NodeList(int val=0,NodeList next = null){this.val = val;this.next = next;}
}public class MyLinkedList {int size;NodeList head;//虚拟头节点public MyLinkedList() {head = new NodeList();size = 0;}public int Get(int index) {if(index<0||index>=size){return -1;}NodeList cur = head;for(int i = 0;i<=index;i++){cur = cur.next;}return cur.val;}public void AddAtHead(int val) {NodeList newNode = new NodeList(val);newNode.next = head.next;head.next = newNode;size++;}public void AddAtTail(int val) {NodeList newNode = new NodeList(val);NodeList cur = head;while(cur.next!=null){cur = cur.next;}cur.next = newNode;size++;}public void AddAtIndex(int index, int val) {if (index > size) return; // 如果 index 超出范围，直接返回if (index < 0) index = 0;NodeList newNode = new NodeList(val);NodeList cur = head;while(index>0){cur = cur.next;index--;}newNode.next = cur.next;cur.next = newNode;size++;}public void DeleteAtIndex(int index) {if(index<0||index>=size){return;}NodeList cur = head;while(index>0){cur = cur.next;index--;}cur.next = cur.next.next;size--;}
}/*** 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);*/

本题是要求将链表进行反转。

我们可以使用双指针，一个cur指针等于头节点，一个pre指针指向空，假设我们向先反转两个指针，可以将cur的next存储在temp临时指针中，然后将cur.next指向pre指针，然后再将cur赋值给pre，和将临时指针赋值给cur，从而进行循环，并加入循环条件为while（cur！=null）。

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int val=0, ListNode next=null) {*         this.val = val;*         this.next = next;*     }* }*/
public class Solution {public ListNode ReverseList(ListNode head) {ListNode cur = head;ListNode pre = null;ListNode temp;while(cur!=null){temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}