Get TLE! Can someone help me out


  • 0
    Y
    public class Solution {
    public ListNode detectCycle(ListNode head) {
        Map<ListNode,Integer> m = new HashMap<>();  //create a hashmap with key is the node and value is the occurrence 
       // store a pointer to the first head
        ListNode copy = head;
        if(head!=null){
        while(head.next!=null){
     //  if there is circle mark it by increment the occurrence  
            if(m.containsKey(head)){
                m.put(head,m.get(head)+1);
            }
            else{// first time occur 
                m.put(head,1);
            }
            head = head.next;
        }
      while(copy.next!=null){//iterate through the linked list to check the occurrence
          if(m.get(copy)==2){ 
              return copy;    
          }
          copy = copy.next;
      }
    }
      return null;
    }
    

    }


  • 1
    M
        while(head.next!=null){
            if(m.containsKey(head)){
                m.put(head,m.get(head)+1);
            }
            else{// first time occur 
                m.put(head,1);
            }
            head = head.next;
        }
    

    Assume there is a cycle. Then you will continue advancing and never hit (head.next == null). While this isn't the most memory efficient way to solve this problem, you want a break; in the if statement so that it will stop. On the other hand, you can just return head at that point instead of incrementing and then searching again.

    public ListNode detectCycle(ListNode head) {
        Map<ListNode,Integer> m = new HashMap<>();
        ListNode copy = head;
        if(head!=null){
           while(head.next!=null){
              if(m.containsKey(head)){
                return head;
              }
              else{
                m.put(head,1);
              }
              head = head.next;
          }
      }
      return null;
    }
    

  • 0
    J

    can you try to solve it without using extra memory as the follow up mentioned?


  • 0
    M

    Step 1: Detect if there is a cycle using fast and slow pointers (fast=fast.next.next, slow=slow.next). If no cycle, return null.

    Step 2: If there is a cycle, advance from the current node until you reach the same node again, keeping track of how many nodes are in the cycle.

    Step 3: Create 2 nodes, with one as far ahead of the other as there are nodes in the cycle. If the cycle is 7 long, one node is 7 nodes ahead of the other.

    Step 4: Advance both forward 1 node at a time until they point to the same node. This node is the start of the cycle, since the distance between the two is exactly the circumference of the cycle. Return this node.


Log in to reply
 

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