Palindrome Linked List
Find the Duplicate Number
Circular Array Loop

---

Remove Nth Node From End of List

뒤에서 N번째 노드를 제거하는 문제

하나의 포인터를 head에서 n만큼의 간격으로 벌려놓고 다른 하나의 포인터는 head를 가르킨다
두개의 포인터를 같은 속도로 움직여 뒤쪽 포인터가 null에 닿았을 때 첫번쨰 포인터가 가르키는 node를 삭제하면 된다

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // Create 2 pointers "n" apart, iterate until end, will be at nth

        ListNode *p1 = head;
        ListNode *p2 = head;
        
        for (int i = 0; i < n; i++) {
            // make p2 "n" apart from p1
            ListNode *temp = p2;
            p2 = temp->next;
        }

        if (p2 == NULL) {
            // the head is what we need to remove
            return head->next;
        }
        
        // increment the pointer until p2->next reaches NULL 
        // then p1 will be (n-1)th node from the end
        while (p2->next != NULL) {
            ListNode *p1_temp = p1;
            ListNode *p2_temp = p2;
            p1 = p1_temp->next;
            p2 = p2_temp->next;
        }

        // remove p1->next
        p1->next = p1->next->next;
        return head;
    }
};

---

Rotate List

k번 만큼 회전한 리스트를 리턴하는 문제

일단 노드가 몇개인지 세고
modulo k 를 했을 떄 숫자만큼을 rotate해준다
잘릴 부분을 찾아서 다시 이어 붙여주는 개념으로 rotate을 구현했다

몇가지 basecase를 주의하자

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0) return head;            //edge case
        if (head == NULL) return head;      //edge case

        //count number of nodes
        int count = 1;
        ListNode *last_node = head;
        while (last_node->next != NULL) {
            count++;
            last_node = last_node->next;
        }

        if (count == 1) return head;         //edge case
        if (k % count == 0) return head;     //edge case

        int rotate = k % count;

        // find cutting point
        ListNode *cut_here = head;
        for (int i = 1; i < count - rotate; i++) {
            cut_here = cut_here->next;
        }

        ListNode *new_head = cut_here->next;
        cut_here->next = NULL;
        last_node->next = head;
        
        return new_head;
    }
};

---

Linked List Cycle

싸이클이 있는지 판단하는 문제

Floyd's Tortoise & Hare 이라는 알고리즘이 있나부다 ,,
이걸쓰면 space complexity가 O(1)에 풀수 있나부다 ,,,

함 보자 ..

slow pointer → shifted by one
fast pointer → shifted by two

만약 사이클이 존재한다면 slow == fast 인 순간이 올 거래 ,, 그것도 in linear time!
왜??

왜냐면 ,, slow pointer 와 fast pointer 사이의 갭이 10이라고 치고,
slow는 +1씩 가고, fast는 +2씩 가니까
5 +1-2 +1-2 ... so on and this will eventually reach 0 (where slow == fast)

why is this linear?
think about the maximum possible gap between slow and fast
it would be number of nodes!
then {number of nodes} +1-2 +1-2 ... so this is linear!

class Solution {
public:
    bool hasCycle(ListNode *head) {
        bool hasCycle(ListNode *head) {
        if (head == NULL) {
            return false;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        
        // when fast and slow are both null, then there is no cycle!
        return false;
    }
    }
};

---

Linked List Cycle II

싸이클이 존재한다면 싸이클의 시작지점의 인덱스를 찾아 리턴하는 문제이다

공식 설명

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }

        if (fast == NULL || fast->next == NULL) return NULL; // no cycle

        while (head != slow) {
            head = head->next;
            slow = slow->next;
        }

        return head;
    }
};