单向链表（带哨兵）
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都不为null
prev.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));
}
}双向链表（带哨兵）
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); // 头部哨兵节点，值为666
tail = new Node(null, 888, null); // 尾部哨兵节点，值为888
head.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));
}
}环形链表（带哨兵）
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); // 初始化哨兵节点，值为-1
sentinel.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 = [] 输出：[]
方法一：
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;
}方法二：
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 输出：[]
方法一：
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;
}方法二：
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]
方法一：
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;
}方法二：
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]
方法一：
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;
}方法二：
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]
方法一：
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;
}
}方法二：
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]
方法一：
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;
}方法二：
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 = [[]] 输出：[]
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 ，返回第二个结点。
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
给你一个单链表的头节点
head，请你判断该链表是否为回文链表
。如果是，返回true；否则，返回false。示例 1：
输入：head = [1,2,2,1] 输出：true示例 2：
输入：head = [1,2] 输出：false
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
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
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 解释：链表中没有环。
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 解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
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;
}
