链表中的经典问题就是链表中是否存在环,存在环,并且求出环的入口节点在哪,链表的中间节点是哪一个.
链表中是否存在环
这道题也有两个解法,用set存储判断法,快慢指针法
set存储判断
还是先来简单版本的,遍历链表,将出现过的节点都放到set中,如果后面有出现过,那就证明这个是有环的,如果循环到最后也没有出现,则认为是没有环
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
Set<ListNode> set = new HashSet<>();
int index = 0;
while(head != null){
//判断是否有环,有的话就直接return true,否则继续
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
//到最后就认为是没有环
return false;
}
}
双指针法解决链表是否有环问题
其实双指针联想到现实场景中,用跑步来是模拟是最好的了
有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。
但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
快慢指针法就是用了这种思想进行判断
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//使用快指针进行判断
while(fast != null){
//这里必须要判断一下，否则就有可能快指针会空指针异常，如果确认有终点，则认为这是没有环
if(fast.next == null){
return false;
}
//快指针走两步
fast = fast.next.next;
//慢指针走一步
slow = slow.next;
//如果相遇的话，则证明有环，否则快指针一定会走到终点
if(fast == slow){
return true;
}
}
return false;
}
}
双指针法判断环的入口是哪一个节点
判断链表中是否有环,并且环的入口是哪一个
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
**说明：**不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
在快慢指针相遇时,这时重新声明一个指针,指向指针头,然后由快指针和第三个指针进行同步走,当两者相遇时,一定是在环的入口
由此得出F = B,所以,当快指针从相遇点开始走的时候,第三个指针从head开始走,当他们相遇时即环的入口
public class Solution {
public ListNode detectCycle(ListNode head) {
//快指针
ListNode fast = head;
//慢指针
ListNode slow = head;
while(fast != null){
//如果快指针到达终点,证明没有环,返回null
if(fast.next == null){
return null;
}
fast = fast.next.next;
slow = slow.next;
//如果有环的话,第三个指针从头开始走,快指针继续走
if(fast == slow){
ListNode third = head;
//当快指针与第三个指针相遇时,证明到了环的入口
while(fast != third){
third = third.next;
fast = fast.next;
}
return third;
}
}
return null;
}
}
双指针法删除倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
这道题核心的点就是如何判断倒数第N个节点在哪里,指针可以停放在那里,因为链表我们是不知道长度的,除非先遍历一遍,知道了长度,就知道倒数第N个节点是哪一个.如果在一次遍历的情况下,这种距离为N场景下,使用双指针法,首先快指针先走N+1步,然后慢指针再与快指针同步走,快指针走到终点时,慢指针这个时候就到了倒数第N+1个节点处,然后slow.next = slow.next.next;即可删除倒数第N个指针节点.
删除倒数第N个节点的情况下,有删除头节点这种特殊情况,如果正常处理比较麻烦,需要判断是不是删除的头结点,但是我们在原有头结点之前,增加一个特殊的哨兵节点,不参与计算和删除,这样即使删除的是头结点,也可以直接按照正常的情况下,返回哨兵节点的next.哨兵节点的作用如图:
代码实现如下:
package com.zhengyao.List.doublepointer;
import com.zhengyao.List.ListNode;
/**
* @author : zhengyao3@郑瑶
* @date : 2019/10/8 16:48
* @Description: 删除链表的倒数第N个节点
* 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
*
* 示例：
*
* 给定一个链表: 1->2->3->4->5, 和 n = 2.
*
* 当删除了倒数第二个节点后，链表变为 1->2->3->5.
* 说明：
*
* 给定的 n 保证是有效的。
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class Solution19 {
public ListNode removeNthFromEnd(ListNode head, int n) {
//哨兵节点
ListNode tempHead = new ListNode(0);
tempHead.next = head;
//快指针
ListNode fast = tempHead;
//慢指针
ListNode slow = tempHead;
int index = 0;
while(fast != null){
//使用双指针法,快指针先走,快指针先走N+1步,这样两者相差步数为n,即找到了需要删除的那个节点,找到之后删除即可
if(index >= n+1 ){
slow = slow.next;
}
index++;
fast = fast.next;
}
//删除节点
slow.next = slow.next.next;
//返回有效节点
return tempHead.next;
}
}