Java O(n) time, O(1) space solution. Temporarily modify the list. With detailed explanation


  • -1
    Q
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null) return null;
    
            // Calculate total length of the linked list
            Return r = reverseList(head);
            if (r.last != head) return null;
            reverseList(head);
            int totalLength = r.count;
            if(totalLength == 1) return null;
    
            // Enter half of the linked list
            int half = (totalLength) / 2;
            ListNode halfNode = head;
            for (int i = 0; i < half; i++) {
                halfNode = halfNode.next;
            }
    
            // Calculate loop length
            ListNode node = halfNode.next;
            int loopLength = 1;
            while (node != halfNode) {
                loopLength++;
                node = node.next;
            }
    
            // Calculate distance from head to loop
            int toLoop = (totalLength - loopLength - 1) / 2;
    
            // Find the node where starting loop
            node = head;
            for (int i = 0; i < toLoop; i++) {
                node = node.next;
            }
            return node;
        }
    
        private Return reverseList(ListNode head) {
            ListNode node = head;
            ListNode lastNode = null;
            int count = 0;
            while (node != null) {
                ListNode next = node.next;
                node.next = lastNode;
                lastNode = node;
                node = next;
                count++;
            }
            Return result = new Return();
            result.last = lastNode;
            result.count = count;
            return result;
        }
    
        private static class Return {
            public ListNode last;
            public int count;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.