链表中环的入口结点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null){
return null;
}
ListNode p1 = pHead;
ListNode p2 = pHead;
while(p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
p2 = pHead;
while (p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}判断有没有环、
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow=head,fast=head;//双指针 ：快慢指针
while (fast!=null && fast.next!=null)
{
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;
}
return false;
}
}
不用快慢指针判断链表中是否有环
方法一：HashSet
定义一个HasshSet用来存放节点的引用，并将其初始化为空，从链表的头节点开始向后遍历，每遍历到一个节点就判断HashSet中是否有这个节点的引用。如果没有，说明这个节点是第一次访问，还没有形成环，那么将这个节点的引用添加到HashSet中去。如果在HashSet中找到了同样的节点，那么说明这个节点已经被访问了，于是就形成了环。这种方法的时间和空间复杂度都为O(N)。
/**
* 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) {
//创建集合对象
HashSet<ListNode> set = new HashSet<ListNode>();
//遍历链表
ListNode p = head;
while (p != null){
if (set.contains(p)){
return true;
}else{
set.add(p);
}
p = p.next;
}
return false;
}
}
题目
一个链表中包含环，请找出该链表的环的入口结点。
思路
思路 1
可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中的环有n个结点，指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向的入口结点时，第一个指针已经围绕着揍了一圈又回到了入口结点。
以下图为例，指针P1和P2在初始化时都指向链表的头结点。由于环中有4个结点，指针P1先在链表上向前移动4步。接下来两个指针以相同的速度在链表上向前移动，直到它们相遇。它们相遇的结点正好是环的入口结点。
现在，关键问题在于怎么知道环中有几个结点呢？
可以使用快慢指针，一个每次走一步，一个每次走两步。如果两个指针相遇，表明链表中存在环，并且两个指针相遇的结点一定在环中。
随后，我们就从相遇的这个环中结点出发，一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数目了。
思路 2
1、哈希表
遍历整个链表，并将链表结点存入哈希表中（这里我们使用容器set），如果遍历到某个链表结点已经在set中，那么该点即为环的入口结点；
2、两个指针
如果链表存在环，那么计算出环的长度n，然后准备两个指针pSlow，pFast，pFast先走n步，然后pSlow和pFase一块走，当两者相遇时，即为环的入口处；
3、改进
如果链表存在环，我们无需计算环的长度n，只需在相遇时，让一个指针在相遇点出发，另一个指针在链表首部出发，然后两个指针一次走一步，当它们相遇时，就是环的入口处。（这里就不说明为什么这样做是正确的，大家可以在纸上推导一下公式）
代码
代码1
public class ListNode {
int val;
/**
*保存链表的值
*/
ListNode next;
/**
*下一个结点
*/
ListNode(int x) {
val = x;
next = null;
}
@Override
public String toString(){
return val+"";
}
}
public class hasCycle {
public static void main(String[] args) {
// test1();
//test2();
test3();
}
// 1->2->3->4->5->6 <-+
// | |
// +---+
private static void test3() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
//ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n3;
// n6.next = n3;
System.out.println(hasCycle(n1));
}
private static void test2() {
// 1->2->3->4->5->6
// ^ |
// | |
// +--------+
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n3;
System.out.println(hasCycle(n1));
}
//1->2->3->4->5->6
private static void test1() {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
System.out.println(hasCycle(n1));
}
public static ListNode hasCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
//首先定义两个指针
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
fast = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
代码2
/**
* 链表中环的入口节点
*
* 思路：
* 1.判断是否存在环，并找到快慢两个指针相遇的位置
* 2.根据找到的这个相遇位置，统计环中节点的数目n，先让快指针走n步，然后快慢两个指针一起运动，快慢指针相遇时的节点就是环的入口节点
*/
public class EnterNodeInLink {
public ListNode getEnterNode(ListNode head){
//参数校验
if(head == null){
return null;
}
//如果有环，第一个和第二个指针在环中相遇时的节点
ListNode meetingNode = meetingNode(head);
int ringLength = 0; //环的长度
if(meetingNode != null){ //如果存在环，就求出环的长度
ListNode tempNode = meetingNode;
meetingNode = meetingNode.next;
while(meetingNode != tempNode){
ringLength++;
meetingNode = meetingNode.next;
}
ringLength++;
}else{ //如果不存在环，就返回null
return null;
}
ListNode ahead = head; //第一个指针
ListNode behind = head; //第二个指针
while(ringLength > 0){
ahead = ahead.next; //第一个指针先在链表上向前移动ringLength步
ringLength--;
}
while(ahead != behind){
ahead = ahead.next;
behind = behind.next;
}
return behind;
}
//在链表存在环的情况下，找到一快一慢两个指针相遇的节点
public ListNode meetingNode(ListNode head){
//参数校验
if(head == null){
return null;
}
ListNode behind = head.next; //后面的指针
//如果只有一个节点直接返回null
if(behind == null){
return null;
}
ListNode ahead = behind.next; //前面的指针
while(behind != null && ahead != null){
if(behind == ahead){
return ahead;
}
//behind指针在链表上移动一步
behind = behind.next;
//ahead指针在链表上移动两步
ahead = ahead.next;
if(ahead != null){
ahead = ahead.next;
}
}
return null;
}
public static void main(String[] args) {
EnterNodeInLink test = new EnterNodeInLink();
ListNode head = new ListNode();
ListNode temp1 = new ListNode();
ListNode temp2 = new ListNode();
ListNode temp3 = new ListNode();
ListNode temp4 = new ListNode();
ListNode temp5 = new ListNode();
head.value=1;
temp1.value=2;
temp2.value=3;
temp3.value=4;
temp4.value=5;
temp5.value=6;
head.next=temp1;
temp1.next=temp2;
temp2.next=temp3;
temp3.next=temp4;
temp4.next=temp5;
temp5.next=null;
ListNode resultNode = test.getEnterNode(head);
if(resultNode != null){
System.out.println(resultNode.value);
}else{
System.out.println("您输入的参数有误！");
}
}
}
class ListNode{
int value;
ListNode next;
}
LeetCode
环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 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) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow=head,fast=head;//双指针 ：快慢指针
while (fast!=null && fast.next!=null)
{
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;
}
return false;
}
}
环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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
解释：链表中没有环。
链表的中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
public ListNode middleNode(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode first = head;
ListNode second = head;
while (second != null && second.next != null){
first = head.next;
second = head.next.next;
}
return first;
}
京公网安备 11010502036488号