单向链表（带哨兵）
java">public class SinglyLinkedList {private Node head = new Node(Integer.MIN_VALUE, null); // 定义一个哨兵节点作为头部节点，避免对头节点进行特殊处理// 节点类，包含值和指向下一个节点的引用private static class Node { int value; // 存储节点的值Node next; // 指向下一个节点的引用public Node(int value, Node next) {this.value = value;this.next = next;}}// 查找指定索引处的节点，使用-1作为起始索引来兼容哨兵节点private Node findNode(int index) {int i = -1; // 从-1开始以适应哨兵节点for(Node curr = this.head; curr != null; curr = curr.next, i++) {if(i == index) {return curr;}}return null; // 如果索引超出范围，则返回null}// 查找最后一个节点private Node findLast() {Node curr;for(curr = this.head; curr.next != null;) { // 遍历直到找到最后一个节点curr = curr.next;}return curr; // 返回最后一个节点}// 在链表末尾添加新节点public void addLast(int value) {Node last = findLast();last.next = new Node(value, null);}// 在指定索引位置插入新节点public void insert(int index, int value) {Node prev = findNode(index - 1); // 找到前一个节点if(prev != null) {prev.next = new Node(value, prev.next); // 插入新节点} else {throw illegalIndex(index); // 如果索引不合法则抛出异常}}// 删除指定索引位置的节点public void remove(int index) {Node prev = findNode(index - 1); // 找到要删除节点的前一个节点Node curr;if(prev != null && (curr = prev.next) != null) { // 确保prev和curr都不为nullprev.next = curr.next; // 删除当前节点} else {throw illegalIndex(index); // 如果索引不合法则抛出异常}}// 在链表头部添加新节点public void addFirst(int value) {this.head.next = new Node(value, this.head.next);}// 创建一个非法索引异常private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}
}双向链表（带哨兵）
java">public class DoublyLinkedListSentinel {// 节点类，包含指向前一个和后一个节点的引用以及存储的值static class Node {Node prev; // 指向前一个节点int value; // 存储节点的值Node next; // 指向下一个节点public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}private final Node head; // 哨兵头节点private final Node tail; // 哨兵尾节点// 构造函数，初始化哨兵头节点和尾节点，并将它们连接起来public DoublyLinkedListSentinel() {head = new Node(null, 666, null); // 头部哨兵节点，值为666tail = new Node(null, 888, null); // 尾部哨兵节点，值为888head.next = tail;tail.prev = head;}// 查找指定索引处的节点，从头节点开始查找private Node findNode(int index) {int i = -1; // 从-1开始以适应哨兵节点for (Node p = head; p != tail; p = p.next, i++) {if (i == index) {return p;}}return null; // 如果索引超出范围，则返回null}// 在链表头部添加新节点public void addFirst(int value) {insert(0, value);}// 删除链表中的第一个节点public void removeFirst() {remove(0);}// 在链表末尾添加新节点public void addLast(int value) {Node pre = tail.prev; // 获取当前最后一个实际节点Node added = new Node(pre, value, tail); // 创建新节点并插入到末尾pre.next = added;tail.prev = added;}// 删除链表中的最后一个节点public void removeLast() {Node removed = tail.prev; // 获取当前最后一个实际节点if (removed == head) { // 如果没有实际节点（只有哨兵）throw illegalIndex(0);}Node prev = removed.prev; // 获取前一个节点prev.next = tail; // 更新前一个节点的next指向尾哨兵tail.prev = prev; // 更新尾哨兵的prev指向新的最后一个实际节点}// 在指定索引位置插入新节点public void insert(int index, int value) {Node prev = findNode(index - 1); // 找到要插入位置的前一个节点if (prev == null || prev.next == tail) { // 确保前一个节点存在且不是尾哨兵throw illegalIndex(index);}Node next = prev.next; // 获取前一个节点的下一个节点Node inserted = new Node(prev, value, next); // 创建新节点并插入prev.next = inserted;next.prev = inserted;}// 删除指定索引位置的节点public void remove(int index) {Node prev = findNode(index - 1); // 找到要删除节点的前一个节点if (prev == null || prev.next == tail) { // 确保前一个节点存在且不是尾哨兵throw illegalIndex(index);}Node removed = prev.next; // 获取要删除的节点Node next = removed.next; // 获取要删除节点的下一个节点prev.next = next; // 更新前一个节点的next指向next.prev = prev; // 更新下一个节点的prev指向}// 创建一个非法索引异常private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}
}环形链表（带哨兵）
java">public class DoublyLinkedListSentinel {// 节点类，包含指向前一个和后一个节点的引用以及存储的值static class Node {Node prev; // 指向前一个节点int value; // 存储节点的值Node next; // 指向下一个节点public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}private final Node sentinel; // 哨兵节点，用于简化边界条件处理// 构造函数，初始化哨兵节点，使其形成一个自循环的环public DoublyLinkedListSentinel() {sentinel = new Node(null, -1, null); // 初始化哨兵节点，值为-1sentinel.next = sentinel; // 将哨兵节点的next指向自己sentinel.prev = sentinel; // 将哨兵节点的prev指向自己}// 在链表头部添加新节点public void addFirst(int value) {Node next = sentinel.next; // 获取当前第一个实际节点Node prev = sentinel; // 哨兵节点作为前一个节点Node added = new Node(prev, value, next); // 创建新节点并插入到头部prev.next = added; // 更新哨兵节点的next指向新节点next.prev = added; // 更新第一个实际节点的prev指向新节点}// 在链表末尾添加新节点public void addLast(int value) {Node prev = sentinel.prev; // 获取当前最后一个实际节点Node next = sentinel; // 哨兵节点作为下一个节点Node added = new Node(prev, value, next); // 创建新节点并插入到末尾prev.next = added; // 更新最后一个实际节点的next指向新节点next.prev = added; // 更新哨兵节点的prev指向新节点}// 删除链表中的第一个节点public void removeFirst() {Node removed = sentinel.next; // 获取第一个实际节点if (removed == sentinel) { // 如果链表为空，抛出异常throw new IllegalArgumentException("非法操作：链表为空");}Node a = sentinel; // 哨兵节点作为前一个节点Node b = removed.next; // 第二个实际节点作为下一个节点a.next = b; // 更新哨兵节点的next指向第二个实际节点b.prev = a; // 更新第二个实际节点的prev指向哨兵节点}// 删除链表中的最后一个节点public void removeLast() {Node removed = sentinel.prev; // 获取最后一个实际节点if (removed == sentinel) { // 如果链表为空，抛出异常throw new IllegalArgumentException("非法操作：链表为空");}Node a = removed.prev; // 获取倒数第二个实际节点Node b = sentinel; // 哨兵节点作为下一个节点a.next = b; // 更新倒数第二个实际节点的next指向哨兵节点b.prev = a; // 更新哨兵节点的prev指向倒数第二个实际节点}// 根据值查找节点private Node findNodeByValue(int value) {Node p = sentinel.next; // 从第一个实际节点开始遍历while (p != sentinel) { // 遍历直到回到哨兵节点if (p.value == value) { // 如果找到目标值，返回该节点return p;}p = p.next; // 继续遍历下一个节点}return null; // 如果没有找到，返回null}// 根据值删除节点public void removeByValue(int value) {Node removed = findNodeByValue(value); // 查找要删除的节点if (removed != null) { // 如果找到了节点Node prev = removed.prev; // 获取前一个节点Node next = removed.next; // 获取后一个节点prev.next = next; // 更新前一个节点的next指向后一个节点next.prev = prev; // 更新后一个节点的prev指向前一个节点}}
}反转单向链表-Leetcode 206
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]
方法一：
java">public ListNode reverseList(ListNode o1) {ListNode n1 = null;ListNode p = o1;while (p != null) {n1 = new ListNode(p.val, n1);p = p.next;}return n1;
}方法二：
java">public ListNode reverseList(ListNode head) {ListNode p=head;if(p!=null || p.next!=null) {return p;}ListNode last=reverseList(p.next);p.next.next=p;p.next=null;return last;}根据值删除节点-Leetcode 203
给你一个链表的头节点
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 输出：[]
方法一：
java">public ListNode removeElements(ListNode head, int val) {ListNode sential=new ListNode(-1,head);ListNode p1=sential;ListNode p2;while((p2=p1.next)!=null) {if(p2.val==val) {p1.next=p2.next;}else {p1=p1.next;}}return sential.next;}方法二：
java">public ListNode removeElements(ListNode head, int val) {if (head == null) {return null;}if (head.val == val) {return removeElements(head.next, val);} else {head.next = removeElements(head.next, val);return head;}
}删除倒数节点-Leetcode 19
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1 输出：[]示例 3：
输入：head = [1,2], n = 1 输出：[1]
方法一：
java">public ListNode removeNthFromEnd(ListNode head, int n) {ListNode sentinel=new ListNode(-1,head);recursion(sentinel, n);return sentinel.next;}
public int recursion(ListNode p,int n) {if(p==null) {return 0;}int nth=recursion(p.next, n);if(nth==n) {p.next=p.next.next;}return nth+1;
}方法二：
java">public ListNode removeNthFromEnd(ListNode head, int n) {ListNode s = new ListNode(-1, head);ListNode p1 = s;ListNode p2 = s;for (int i = 0; i < n + 1; i++) {p2 = p2.next;}while (p2 != null) {p1 = p1.next;p2 = p2.next;}p1.next = p1.next.next;return s.next;
}有序链表去重-Leetcode 83
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。示例 1：
输入：head = [1,1,2] 输出：[1,2]示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
方法一：
java">public ListNode deleteDuplicates(ListNode head) {if(head==null || head.next==null) {return head;}ListNode p1=head;ListNode p2;while((p2=p1.next)!=null) {if(p1.val==p2.val) {p1.next=p2.next;}else {p1=p1.next;}}return head;
}方法二：
java">public ListNode deleteDuplicates(ListNode p) {if (p == null || p.next == null) {return p;}if(p.val == p.next.val) {return deleteDuplicates(p.next);} else {p.next = deleteDuplicates(p.next);return p;}
}有序链表去重-Leetcode 82
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]
方法一：
java">public ListNode deleteDuplicates(ListNode p) {if (p == null || p.next == null) {return p;}if (p.val == p.next.val) {ListNode x = p.next.next;while (x != null && x.val == p.val) {x = x.next;}return deleteDuplicates(x);} else {p.next = deleteDuplicates(p.next);return p;}
}方法二：
java">public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode s = new ListNode(-1, head);ListNode p1 = s;ListNode p2;ListNode p3;while ((p2 = p1.next) != null && (p3 = p2.next) != null) {if (p2.val == p3.val) {while ((p3 = p3.next) != null && p3.val == p2.val) {}p1.next = p3;} else {p1 = p1.next;}}return s.next;
}合并有序链表-Leetcode 21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
方法一：
java">public ListNode mergeTwoLists(ListNode p1, ListNode p2) {ListNode s = new ListNode(-1, null);ListNode p = s;while (p1 != null && p2 != null) {if (p1.val < p2.val) {p.next = p1;p1 = p1.next;} else {p.next = p2;p2 = p2.next;}p = p.next;}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return s.next;
}方法二：
java">public ListNode mergeTwoLists(ListNode p1,ListNode p2){if (p2==null){return p1;}if(p1==null){return p2;}if (p1.val<p2.val){p1.next=mergeTwoLists(p1.next,p2);return p1;}else{p2.next=mergeTwoLists(p1,p2.next);return p2;}
}合并多个有序链表-Leetcode 23
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [1->4->5,1->3->4,2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]
java">public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}return split(lists, 0, lists.length - 1);
}public ListNode split(ListNode[] lists, int i, int j) {System.out.println(i + " " + j);if (j == i) {return lists[i];}int m = (i + j) >>> 1;return mergeTwoLists(split(lists, i, m),split(lists, m + 1, j));
}
public ListNode mergeTwoLists(ListNode p1,ListNode p2){if (p2==null){return p1;}if(p1==null){return p2;}if (p1.val<p2.val){p1.next=mergeTwoLists(p1.next,p2);return p1;}else{p2.next=mergeTwoLists(p1,p2.next);return p2;}
}查找链表中间节点-Leetcode 876
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
java">public ListNode middleNode(ListNode head) {ListNode p1 = head; // 慢指针，中间点ListNode p2 = head; // 快指针while (p2 != null && p2.next != null) {p1 = p1.next;p2 = p2.next;p2 = p2.next;}return p1;
}回文链表-Leetcode 234
回文链表
。如果是，返回true；否则，返回false。示例 1：
输入：head = [1,2,2,1] 输出：true示例 2：
输入：head = [1,2] 输出：false
java">public boolean isPalindrome(ListNode head) {if(head==null || head.next==null) {return true;}ListNode p1=head;ListNode p2=head;ListNode o1=p1;ListNode n1=null;while(p2!=null && p2.next!=null) {p1=p1.next;p2=p2.next;p2=p2.next;o1.next=n1;n1=o1;p1=o1;}if(p2!=null) {p1=p1.next;}while(n1!=null) {if(n1.val!=p1.val) {return false;}p1=p1.next;n1=n1.next;}return true;
}环形链表-Leetcode 141
如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
java">public boolean hasCycle(ListNode head) {ListNode h = head; // 兔ListNode t = head; // 龟while (h != null && h.next != null) {t = t.next;h = h.next.next;if(h == t){return true;}}return false;
}环形链表-Leetcode 142
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。提示：
java">public ListNode detectCycle(ListNode head) {ListNode t=head;ListNode h=head;while(h!=null && h.next!=null) {t=t.next;h=h.next.next;if(t==h) {t=head;while(true) {if(h==t) {return h;}h=h.next;t=t.next;}}}return null;
}
