8.10 算法刷题【1道题】

22. 链表中环的入口结点（快慢指针）

原题链接

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *entryNodeOfLoop(ListNode *head) {if (!head || !head->next) return 0;ListNode *first = head, *second = head;while (first && second){first = first->next;second = second->next;if (second) second = second->next;else return 0;if (first == second){first = head;while (first != second){first = first->next;second = second->next;}return first;}}return 0;}
};

巧就巧在巧*****的找到相遇位置之后，重新初始化一个指针去走，最后会相遇在入口处。（可以用数学证明）
class Solution {private ListNode hasCycle(ListNode head){if(head == 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){return slow;}}return null;}public ListNode entryNodeOfLoop(ListNode head) {ListNode slow = hasCycle(head);if(slow == null){return null;}ListNode fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return slow;}
}