数据结构-链表笔记

移除节点

203. 移除链表元素 - 力扣（LeetCode）

/*** 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) {// 创建一个虚拟头节点，方便处理删除头节点的情况ListNode dummyHead = new ListNode();dummyHead.next = head;// 初始化双指针ListNode pre = dummyHead; // pre指向当前节点的前一个节点ListNode cur = head;      // cur指向当前节点// 遍历链表while (cur != null) {// 如果当前节点的值等于要删除的值if (cur.val == val) {// 跳过当前节点，直接链接前一个节点到当前节点的下一个节点pre.next = cur.next;} else {// 如果当前节点的值不等于要删除的值，更新 pre 指针为当前节点pre = cur;}// 无论当前节点的值是否被删除，都移动 cur 指针到下一个节点cur = cur.next;}// 返回新的头节点，跳过虚拟头节点return dummyHead.next;}
}

设计链表

在链表类中实现这些功能：得到第 index 个节点的值，

在链表的第一个元素之前添加一个值为 val 的节点，

将值为 val 的节点追加到链表的最后一个元素，

在链表中的第 index 个节点之前添加值为 val 的节点，

删除链表中的第 index 个节点

707. 设计链表 - 力扣（LeetCode）

解法:单链表

class ListNode {int val; // 节点的值ListNode next; // 指向下一个节点的指针ListNode() {} // 默认构造函数ListNode(int val) { // 带值的构造函数this.val = val;}
}class MyLinkedList {// size 存储链表元素的个数int size;// 虚拟头结点，便于处理头节点的插入和删除ListNode dummyHead;public MyLinkedList() {size = 0; // 初始化链表大小为 0dummyHead = new ListNode(0); // 创建虚拟头结点}// 获取链表中第 index 个节点的值，索引从 0 开始public int get(int index) {// 检查索引是否有效if (index < 0 || index >= size) {return -1; // 返回 -1 表示索引无效}ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的节点for (int i = 0; i <= index; i++) {curNode = curNode.next; // 移动到下一个节点}return curNode.val; // 返回目标节点的值}// 在链表头部添加一个新节点public void addAtHead(int val) {ListNode newNode = new ListNode(val); // 创建新节点newNode.next = dummyHead.next; // 新节点指向当前头节点dummyHead.next = newNode; // 虚拟头节点指向新节点size++; // 更新链表大小}// 在链表尾部添加一个新节点public void addAtTail(int val) {ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到链表尾部while (curNode.next != null) {curNode = curNode.next; // 移动到下一个节点}ListNode newNode = new ListNode(val); // 创建新节点curNode.next = newNode; // 尾节点指向新节点size++; // 更新链表大小}// 在指定索引处添加一个新节点public void addAtIndex(int index, int val) {// 如果索引大于链表大小，无法添加if (index > size) {return;}// 如果索引小于 0，从头部插入if (index < 0) {index = 0;}ListNode newNode = new ListNode(val); // 创建新节点ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的前一个节点for (int i = 0; i < index; i++) {curNode = curNode.next; // 移动到下一个节点}// 插入新节点newNode.next = curNode.next; // 新节点指向当前位置的下一个节点curNode.next = newNode; // 前一个节点指向新节点size++; // 更新链表大小}// 删除指定索引的节点public void deleteAtIndex(int index) {// 检查索引是否有效if (index < 0 || index >= size) {return; // 索引无效，不进行任何操作}size--; // 先减少链表大小ListNode curNode = dummyHead; // 从虚拟头节点开始// 遍历到目标索引的前一个节点for (int i = 0; i < index; i++) {curNode = curNode.next; // 移动到下一个节点}// 删除目标节点curNode.next = curNode.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);*/

双指针

反转链表

206. 反转链表 - 力扣（LeetCode）

class Solution {// 反转链表的核心方法，传入链表的头节点 headpublic ListNode reverseList(ListNode head) {// 如果链表为空或链表只有一个节点，则不需要反转，直接返回原链表的头节点if (head == null || head.next == null) {return head;  // 终止条件：空链表或只有一个节点}// 初始化两个指针：pre 用来跟踪已经反转的部分，cur 用来跟踪未反转的部分ListNode pre = head;   // pre 指向当前节点，初始时为链表的头节点ListNode cur = head.next;   // cur 指向下一个节点，初始时为头节点的下一个节点// 将头节点的 next 设为 null，因为反转后原来的头节点会成为尾节点，尾节点的 next 应该是 nullhead.next = null;// 开始遍历链表，直到 cur 为空（即链表末尾）while (cur != null) {ListNode temp = cur.next;   // 暂存 cur 的下一个节点，防止链表断开后丢失后续节点cur.next = pre;   // 将当前节点 cur 的 next 指向 pre，从而实现反转pre = cur;   // pre 前进到 cur，表示反转后的部分已经包括当前节点cur = temp;   // cur 前进到下一个节点（即之前暂存的节点），继续反转}// 当 cur 为 null 时，pre 指向的是反转后的新头节点，返回该节点return pre;}
}

两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

// 定义链表节点类
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 swapPairs(ListNode head) {// 定义一个虚拟头节点 dummyHead，用来简化链表头部的操作ListNode dummyHead = new ListNode(0);  // 虚拟头节点，值为0，指向实际链表的头节点dummyHead.next = head;  // 将虚拟头的 next 指向传入的 head，便于处理链表的开头// 定义临时指针 temp，用来遍历链表。初始指向 dummyHead，方便处理链表头部ListNode temp = dummyHead;// node1 和 node2 分别用于指向要交换的两个相邻节点ListNode node1;ListNode node2;// 只要 temp 后面有两个节点存在（即 temp.next 和 temp.next.next 都不为空），就可以继续交换while (temp.next != null && temp.next.next != null) {// node1 指向第一对中第一个节点node1 = temp.next;// node2 指向第一对中第二个节点node2 = temp.next.next;// 开始交换：将 temp 的 next 指向第二个节点（node2）temp.next = node2;// 将第一个节点 node1 的 next 指向第二个节点 node2 的下一个节点，即交换后第一个节点应该指向的节点node1.next = node2.next;// 将第二个节点 node2 的 next 指向第一个节点 node1，完成交换node2.next = node1;// 将 temp 指向 node1，继续处理下一对temp = node1;  // node1 是交换后的第二个节点，所以 temp 移动到这里准备处理下一对节点}// 返回新链表的头节点，即 dummyHead 的 nextreturn dummyHead.next;  // dummyHead 是虚拟头节点，实际链表的头节点在 dummyHead.next}
}

删除链表的倒数第N个节点

代码随想录 (programmercarl.com)

// 定义链表节点类
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 {// 移除链表中倒数第 n 个节点public ListNode removeNthFromEnd(ListNode head, int n) {// 边界检查，如果链表为空，直接返回 nullif (head == null) {return null;}// 定义一个虚拟头节点，dummyHead 用来处理链表头部的特殊情况（例如删除头节点）ListNode dummyHead = new ListNode(0);dummyHead.next = head; // dummyHead.next 指向链表头节点// 定义快指针 fast 和慢指针 slow，都初始化为 dummyHeadListNode fast = dummyHead;ListNode slow = dummyHead;// 快指针 fast 先前进 n+1 步，以便与慢指针 slow 之间的距离为 nfor (int i = 0; i <= n; i++) {fast = fast.next;}// 快慢指针同时向前移动，直到 fast 到达链表末尾while (fast != null) {fast = fast.next;slow = slow.next;}// 此时慢指针 slow 指向待删除节点的前一个节点，执行删除操作slow.next = slow.next.next;// 返回新的链表头节点（dummyHead.next），此时 dummyHead.next 是链表的头节点return dummyHead.next;}
}

哈希表

判断是否存在同一个元素

链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

public class Solution {// 定义一个方法来获取两个链表的交点节点public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 使用一个 HashSet 来存储链表 A 的所有节点Set<ListNode> hashset = new HashSet<ListNode>();// 创建一个指针 cur，用于遍历链表 AListNode cur = headA;// 遍历链表 A，直到链表的末尾while(cur != null){// 将当前节点添加到 HashSet 中hashset.add(cur);// 移动到下一个节点cur = cur.next;}// 重新使用 cur 指针遍历链表 Bcur = headB;// 遍历链表 B，直到链表的末尾while(cur != null){// 如果当前节点在 HashSet 中，说明找到了交点if(hashset.contains(cur)){// 返回交点节点return cur;}// 移动到下一个节点cur = cur.next;}// 如果没有交点，返回 nullreturn null;}
}

环形链表

142. 环形链表 II - 力扣（LeetCode）

public class Solution {public ListNode detectCycle(ListNode head) {// 创建一个 HashSet 用来存储访问过的节点Set<ListNode> hashset = new HashSet<>();// 初始化当前节点为链表的头节点ListNode cur = head;// 循环遍历整个链表while (cur != null) {// 如果当前节点已经存在于 HashSet 中，说明链表有环，且该节点就是环的起点if (hashset.contains(cur)) {return cur;  // 返回环的起点节点} else {// 如果当前节点不在 HashSet 中，将其添加到集合中，表示已经访问过该节点hashset.add(cur);}// 移动当前指针到下一个节点cur = cur.next;}// 如果遍历完整个链表都没有找到重复的节点，说明链表无环，返回 nullreturn null;}
}