Leetcode 142) Linked List Cycle II

12 Jun 2021 in Algorithms

내 풀이

• arraylist에 저장해서 contains, indexOf 사용. 객체저장해서 그 객체를 이미 가지고 있으면 return true 아니면 pointer가 null될때까지도 겹치는 게 없으면 fasle

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){return null;}
        List<ListNode> res = new ArrayList<>();
        res.add(head);
        while(head.next!=null){
            if(res.contains(head.next)){
                return head.next;
            }else{
                res.add(head.next);
            }
            head=head.next;
        }

        return null;

    }


}

다른 답안

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
            return null;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow!=fast && fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(slow==fast){
            slow=head;
            while(fast.next!=slow){
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }
        
        return null;
        
    }
}

/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode res = head;
        //조건들, 안에 명령문들에 null ptr 에러 안 뜨게 방지하는 역할
        while(fast!=null && fast.next!=null && slow!=null){
            fast= fast.next.next;
            slow = slow.next;
            if(fast==slow){
                while(res!=slow){
                    res = res.next;
                    slow = slow.next;
                }
                return res;
            }
        }
        return null;
    }
}