剑指offer16
2019-07-08 本文已影响0人
MonarchNie
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解题思路分析
- 首先我们应该判断链表中是否有环,利用一个快慢指针,如果快指针最后还碰上了慢指针就说明链表中有环
- 然后我们需要找到环的入口节点,利用前面一步找到的环,当然前面肯定是在环中相遇的,所以利用前面找到的环中的节点,先计算出环的长度,然后使一个指针先从头走环的长度那么长,然后使另一个指针从头开始走,最后两个指针会相遇在环的入口节点。
代码实现
public ListNode entryNodeOfLoop(ListNode pHead) {
if (pHead == null) {
return null;
}
//先找到环中的某个节点
ListNode meetingNode = meetingNode(pHead);
int count = 1;
ListNode node = meetingNode;
//计算环中的节点个数
while (node.next != meetingNode) {
count++;
node = nodex.next;
}
ListNode node1 = pHead, node2 = pHead;
//先让一个节点走节点个数步
for (int i = 0; i < count; i++) {
node1 = node1.next;
}
//开始找到环的入口节点
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node2;
}
//返回环中的节点
public ListNode meetingNode(ListNode pHead) {
//分别声明快指针和慢指针
ListNode slow = pHead, fast = pHead.next;
while (fast != null) {
if (fast == slow) {
return fast;
}
slow = slow.next;
fast = fast.next;
//防止空指针异常
if (fast != null) {
fast = fast.next;
}
}
return null;
}