目录
1. 环形链表
解题思路
2. 环形链表 II
解题思路
3. 删除排序链表中的重复元素
解题思路
4. 删除排序链表中的重复元素 II
解题思路
5. 移除链表元素
解题思路
6. 链表的中间结点
解题思路
1. 环形链表
OJ：环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路
快慢指针
快指针走两步，慢指针走一步，如果链表带环，两个最终肯定会在环内相遇；如果链表不带环，快指针肯定会走到链表的末尾
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode low = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
low = low.next;
if(fast == low){
return true;
}
}
return false;
}2. 环形链表 II
OJ：环形链表 II
给定一个链表的头节点 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
解释：链表中没有环。
解题思路
public ListNode detectCycle(ListNode head) {
// 快慢指针相遇时，引入新节点从链表头开始，慢的一定会和新节点在环形第一个节点相遇
ListNode low = head;
ListNode fast = head;
while (fast != null && fast.next != null){
low = low.next;
fast = fast.next.next;
if(fast == low){
ListNode third = head;
while (third != low){
third = third.next;
low = low.next;
}
return low;
}
}
return null;
}3. 删除排序链表中的重复元素
OJ：删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
解题思路
- 思路1
由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。当cur与cur.next的元素相等时，删除cur.next。下面给出了两种实现方法。
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
// 至少有两个节点
// 头节点val在范围之外
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}public ListNode deleteDuplicates(ListNode head) {
if(head ==null ||head.next == null){
return null;
}
head = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}4. 删除排序链表中的重复元素 II
OJ：删除排序链表中的重复元素 II
给定一个已排序的链表的头
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 head) {
// 1.base case
if (head == null || head.next == null) {
return head;
}
ListNode dummyHead = new ListNode(-101);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode cur = prev.next;
while (cur != null) {
ListNode sec = cur.next;
if (sec == null) {
break;
}
if (cur.val != sec.val) {
prev = prev.next;
}else {
// 此时cur和sec相等
while (sec != null && cur.val == sec.val) {
sec = sec.next;
}
// 此时sec一定走到第一个和cur不相等的结点
// prev .. sec全都是待删除的结点
prev.next = sec;
}
cur = sec;
}
return dummyHead.next;
} //递归法
// 传入一个以head为头节点的链表，就能删除其中所有的重复元素，重复元素一个都不保留
public ListNode deleteDuplicates(ListNode head) {
// 1.base case
if(head == null || head.next == null) {
return head;
}
if(head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
}else {
// 头节点就是重复的节点，先处理完头节点的情况
ListNode newHead = head.next;
while(newHead != null && newHead.val == head.val) {
newHead = newHead.next;
}
// 此时newHead一定不是待删除的结点，最终整个传入函数，返回更新后的值即可
return deleteDuplicates(newHead);
}
}5. 移除链表元素
OJ：移除链表元素
给你一个链表的头节点
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
输出：[]
解题思路
（1）先判断头节点元素是否与val相等，相等删除头节点（head = head.next）
（2）判断后面的节点元素是否与val相等，相等删除（prev.next = prev.next.next;）；不相等往下继续遍历。直至到链表尾部。
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
// 有头节点的链表解法
ListNode dummyHead = new ListNode();
//与原链表建立联系
dummyHead.next = head;
ListNode prev = dummyHead;
while(prev.next != null){
if(prev.next.val == val){
prev.next = prev.next.next;
}else{
prev = prev.next;
}
}
return dummyHead.next;
}public ListNode removeElements(ListNode head, int vals) {
if(head == null){
return null;
}
head.next = removeElements(head.next,vals);
return head.val == vals ? head.next :head;
}6. 链表的中间结点
给你单链表的头结点
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 ，返回第二个结点。
解题思路
- 思路1
快慢指针，慢指针走一步，快指针走两步，当快指针走到链表最后一个或走到空时，慢指针走到中间节点。
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode low = head;
while (fast!= null && fast.next != null){
low = low.next;
fast = fast.next.next;
}
return low;
}- 思路2
先求出链表长度，再除以2，就是中间节点的位置了，从链表头遍历到该位置再返回。
public ListNode middleNode(ListNode head) {
int length = 0;
ListNode node = head;
while(node != null){
length++;
node = node.next;
}
length = length / 2;
node = head;
for(int i =0;i<length;i++){
node = node.next;
}
return node;
}
