数据结构与算法-链表

单向链表（带哨兵）

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));}
}

双向链表（带哨兵）

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));}
}

环形链表（带哨兵）

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 = []
输出：[]

 方法一：

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 <= 105
• pos 的值为 -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;
}