[Day4/75] LeetCode 75

876. Middle of the Linked List

해당 노드의 가운데 헤드를 찾는 문제이다. 만약 중간 값이 두가지라면 뒤의 값을 반환.

문제를 해결하기 위해 보통 두가지 방법이 있다.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode A = head;
        ListNode B = head;
        while(B!=null && B.next != null){
            B = B.next.next;
            A = A.next;
        }
        return A
    }
}

문제 풀이 (1) - Fast and Slow Pointer

1. Fast and Slow Pointer 라는 방법이 있다.
2. B의 노드가 두 칸을 갈때, A의 노드는 한 칸씩 가는 방법이다.
3. B가 마지막에 도달 했을 때 A노드의 헤드가 중간 값이다. 

class Solution {
    public ListNode middleNode(ListNode head) {
        int len =0;
        ListNode temp = head;
        while(head!=null){
            head = head.next;
            len++;
        }
        int i =0;
        int half = len/2;
        while(i<half){
            temp = temp.next;
            i++;
        }
        return temp;
    }
}

문제 풀이 (2)

1. 기존 node의 전체 길이를 구해준다.
2. 전체 길이의 절반만큼 while문을 돌며 중간 값의 노드를 구해준다.

---

142. Linked List Cycle II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next==null){
            return null;
        }
        Set<ListNode> nodes = new HashSet<>();
        ListNode node = head;
        while(node!=null){
            if(nodes.contains(node)){
                return node;
            }
            nodes.add(node);
            node=node.next;
        }
        return null;
    }
}