链表与环的一些题目

返回两个链表的第一个公共节点

两个链表的第一个公共结点_牛客题霸_牛客网

其实这一题主要的思想也是跟环类似，一共走两轮。

        第一轮谁先走到null，谁变成另一个链表的头结点继续走，这一轮可以确定偏移量

        第二轮就是代表二者到达终点的距离相等，因为(x1 + x + x2) = x2 + x + x1，所以到达交点的距离也是相同的

其实这道题也是找偏移量的过程 

  public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1,cur2 = pHead2;
        while(cur1 != cur2){
            cur1 = cur1 == null? pHead2: cur1.next;
            cur2 = cur2 == null? pHead1: cur2.next;
        }
        return cur1;
    }

 判断链表是否有环

. - 力扣（LeetCode）

主要思路: 快慢指针，慢指针能追上快指针就代表有环，因为快指针是慢指针的二倍 

  public boolean hasCycle(ListNode head) {
       if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow){
             if (fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

  判断链表环的位置

. - 力扣（LeetCode）

一共走两轮，第二轮的交点就是环的入口

        第一轮走到相交位置，慢指针变成链表的头结点继续走

        第二轮同时都是移动一格，相交点就是环的入口

思路就是下图

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    // 如果链表中不存在环
    if (fast == null || fast.next == null) {
        return null;
    }
    // fast回到终点继续走
    fast = head;
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

非常感谢您的支持和鼓励！制作博客确实需要付出很多心血，尤其是分享个人经验和解决问题的方法。如果我的回答对您有帮助，我会很高兴为您点个三连。另外，祝您周末愉快，愿您的每一天都充满快乐和成就！