[leetcode] Summary of Linked List (1)

오늘 leetcode에서 Linked List와 관련된 제목을 정리합니다.
1. Reverse Linked List
제목 대의: 단일 체인 테이블을 반전시킨다(귀속과 교체를 각각 고려할 수 있다)
기본 사고방식:
(1) 귀환 방식은 어떤 반전을 기다리는 리스트에 대해 먼저 귀환 호출 함수를list->next의 반전을 받은 다음list->next 노드에 추가하면 된다.귀환 출구는 반전된 체인 시계의 머리 지침을 되돌려줍니다. 원시 체인 시계의 머리 지침은 마지막 노드가 되어 반드시 비워야 합니다.

ListNode* reverseList(ListNode* head) {
        if(NULL == head || NULL == head->next) 
        {
            return head;
        }
        ListNode *newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }

(2) 교체 방식의 기본 방법은 유사하여 더 이상 군말하지 않는다.

ListNode* reverseList(ListNode* head) {
        if(NULL == head || NULL == head->next) 
        {
            return head;
        }
        ListNode *ptr = head->next;
        head->next = NULL;
        while(ptr)
        {
            ListNode *tmp = ptr->next;
            ptr->next = head;
            head = ptr;
            ptr = tmp;
        }
        return head;
    }

2. Reverse Linked List II
제목 대의: 1과 달리 여기에 하나의list를 제시할 뿐만 아니라 두 위치의 m와 n(1≤m≤n≤length oflist.)도 제시한다.m와 n 사이의 일부 노드만 반전할 것을 요구합니다.그리고 in-place와 one-pass를 요구합니다.
기본적인 사고방식: 나의 방법은 어디까지 훌륭하지 않다. 단지 간단하게 훑어보았을 뿐이다. m와 n 사이의 노드를 만나면 반전을 한다. 주의해야 할 것은 m와 n 사이의 이 부분의 머리와 꼬리 부분은 마지막에 원시 체인 시계와 연결되어야 한다.

ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *pre = NULL, *next, *ptr;
        ListNode *pPre = NULL, *ptail, *phead;
        ptr = head;
        int cnt = 1;
        while(ptr)
        {
            if(cnt >= m && cnt <= n)
            {
                if(cnt == m) ptail = ptr;
                if(cnt == n) phead = ptr;
                next = ptr->next;
                if(pPre) ptr->next = pPre;
                pPre = ptr;
                ptr = next;
            } else if(cnt < m){
                pre = ptr;
                ptr = ptr->next;
            } else {
                ptr = ptr->next;
            }
            ++cnt;
        }
        if(pre)
        {
            pre->next = phead;
            ptail->next = next;
        } else {
            head = phead;
            ptail->next = next;
        }
        return head;
    }

3. Remove Nth Node From End of List
제목 대의: 체인 테이블의 밑에서 n번째 노드를 삭제하고 제목은 n이 유효하다는 것을 보증하며 체인 테이블을 한 번만 훑어보아야 한다.
기본적인 사고방식: 빠른 바늘과 느린 바늘을 유지하고 빠른 바늘은 처음에 느린 바늘보다 n보를 더 걷는다. 이렇게 하면 빠른 바늘이 종점에 도달할 때 느린 바늘은 삭제할 노드에 도달한다.삭제 작업은 삭제된 노드의 앞 노드를 알아야 하기 때문에 (당연히 모르는 상황에서도 할 수 있다. 한 문제 참조) 빠른 바늘이 체인 시계의 끝점에 도달할 때 느린 바늘이 삭제된 노드의 앞 노드에 꼭 맞다.그럼 문제가 생겼어요. 헤드 노드가 삭제되면 어떡해요?그래서 헤드 노드 앞에 빈 노드를 추가해야 한다.

ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL) return head;
        ListNode *empty = new ListNode(0);
        empty->next = head;
        ListNode *slow = empty;
        ListNode *fast = head;
        while(fast != NULL && n > 0)
        {
            fast = fast->next;
            --n;
        }
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        fast = slow->next;
        slow->next = fast->next;
        delete(fast);
        head = empty->next;
        delete(empty);
        return head;
    }

4. Delete Node in a Linked List
제목 대의: 체인 테이블의 어느 노드를 가리키는 바늘만 제시하고 이 노드를 삭제할 것을 요구합니다.주의 제목에서 한 가지를 강조했다. 이 노드가 꼬리 노드일 리가 없다.
기본적인 사고방식: 제목을 보면 체인 시계의 머리 지침도 주지 않고 끝 노드를 삭제할 수 없다고 강조하면 우리는 val을 바꾸는 전략을 사용할 수 있다.삭제할 노드의next 노드의 값을 이 노드에 복사한 다음next 노드를 삭제합니다.

void deleteNode(ListNode* node) {
        if(node == NULL) return;
        node->val = node->next->val;
        ListNode *tmp = node->next;
        node->next = node->next->next;
        delete(tmp);
    }

5. Palindrome Linked List
제목의 대의: 주어진 체인 테이블이 회문인지 아닌지를 판단한다.가장 좋은 것은 O(n)의 시간과 O(1)의 공간이다.
기본적인 사고방식: 빠른 바늘과 느린 바늘을 유지하고 느린 바늘은 한 걸음씩 걷는다. 빠른 바늘은 두 걸음씩 걷는다. 이렇게 하면 빠른 바늘이 종점에 도착할 때 느린 바늘이 중점에 딱 맞다. 그러면 이 체인 시계를 긴 두 부분으로 나누기 쉽다.회문 여부를 판단하기 위해서는 전반의 역순과 후반의 정서가 일치하는지 여부다.따라서 느린 바늘이 움직이는 동시에 앞부분의 체인 시계를 반전시키면 된다.

bool compareTwoLists(ListNode* head1, ListNode *head2) {
        ListNode *ptr1 = head1;
        ListNode *ptr2 = head2;
        if(NULL == ptr1 && NULL == ptr2) return true;
        while(ptr1 && ptr2)
        {
            if(ptr1->val != ptr2->val) return false;
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        if(NULL != ptr1 || NULL != ptr2) return false;
        else return true;
    }
    
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *pre = NULL;
        
        while(fast && fast->next)
        {
            fast = fast->next->next;
            
            ListNode *tmp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = tmp;
        }
        ListNode *list1 = pre;
        ListNode *list2 = slow;
        if(fast != NULL) list2 = slow->next; 
        return compareTwoLists(list1, list2);
    }

6. Intersection of Two Linked Lists
제목의 대의: 두 체인 시계가 교차하는 교점을 판단한다.
기본적인 사고방식: 두 개의 체인 시계를 한 번씩 훑어보고 각자의 길이 m와 n을 찾아낸다.그리고 길이가 비교적 큰 체인 시계의 바늘을 abs(m-n)보로 먼저 걷고 두 바늘을 함께 걷는다. 바늘이 종점에 도착할 때 느린 바늘은 교점의 위치에 딱 맞다.

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(NULL == headA) return headA;
        if(NULL == headB) return headB;
        int lenA = 0, lenB = 0;
        ListNode *pA = headA, *pB = headB;
        while(pA)
        {
            ++lenA;
            pA = pA->next;
        }
        while(pB)
        {
            ++lenB;
            pB = pB->next;
        }
        pA = headA;
        pB = headB;
        while(lenA > lenB)
        {
            --lenA;
            pA = pA->next;
        }
        while(lenB > lenA)
        {
            --lenB;
            pB = pB->next;
        }
        while(pA && pB)
        {
            if(pA == pB) return pA;
            pA = pA->next;
            pB = pB->next;
        }
        ListNode *ret = NULL;
        return ret;

7. Remove Linked List Elements
제목 대의: 체인 테이블에서 노드 값이 지정한 요소의 모든 노드와 같은 것을 삭제합니다.
기본적인 사고방식: 한 번 훑어보고 삭제할 노드를 삭제한다.주의해야 할 것은 헤드 노드는 단독으로 처리해야 하기 때문에 보초병 노드를 헤드 노드 앞에 추가할 수 있다.

ListNode* removeElements(ListNode* head, int val) {
        if(head == NULL) return head;
        ListNode *empty = new ListNode(0);
        empty->next = head;
        ListNode *ptr = empty;
        while(ptr->next)
        {
            if(ptr->next->val == val)
            {
                ListNode *tmp = ptr->next;
                ptr->next = tmp->next;
                delete(tmp);
            } else ptr = ptr->next;
        }
        head = empty->next;
        delete(empty);
        return head;
    }

8. Linked List Cycle
제목의 대의: 하나의 체인 테이블에 고리가 있는지, O(1)의 공간 복잡도를 판단한다.
기본적인 사고방식: 체인 시계에 고리가 존재한다고 가정하면 우리는 느린 지침과 빠른 지침(매번 두 걸음씩)을 함께 출발시키면 빠른 지침은 결국 느린 지침을 따라잡을 것이다.

bool hasCycle(ListNode *head) {
        if(head == NULL) return false;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow -> next;
            fast = fast->next->next;
            if(fast == slow) return true;
        }
        return false;
    }

9. Linked List Cycle II
제목의 대의: 체인 테이블에 고리가 있는지 없는지를 판단해야 할 뿐만 아니라 고리가 시작되는 위치도 지적해야 한다.
기본적인 사고방식: 다음은 8중 속도 느린 지침이 만나는 위치와 고리의 시작 위치의 관계를 간단하게 분석해 보겠다.
간단하게 보기 위해서, 우리는 빠른 바늘이 느린 바늘보다 한 바퀴 더 갔다고 가정한다. (그림을 그릴 수 있고, 더욱 쉽게 알아볼 수 있다.)가령 체인 시계의 고리 길이가 L이라고 가정하면 속도 바늘의 만남 위치와 고리의 시작 위치에 따라 우리는 고리를 두 부분으로 나눌 수 있다. 시작점에서 만남점까지의 길이는 L1이고 만남점에서 시작점까지의 길이는 L2이다. (이곳의 거리는 체인 시계의 방향을 따라 계산된다는 것을 주의한다).체인 테이블의 비고리 부분의 길이는 N이다.
그러면 만나면 빠른 포인터의 길이는 N+L1+L2+L1, 느린 포인터의 길이는 N+L1이고 그 중에서 N+L1+L2+L1=2(N+L1)이기 때문에 L2=N이 있다.즉 만남점에서 출발점까지의 거리는 체인 헤드에서 출발점까지의 거리와 같다.
위쪽은 특례입니다. 만약에 빠른 바늘이 느린 바늘보다 x바퀴를 더 걷는다면 비슷한 등식이 있지 않을까요?
N + x*(L1+L2) + L1 = 2 * (N + L1)
x*(L1+L2) = N + L1
(x-1)(L1+L2) + L2 = N
이 스타일은 또 무슨 뜻입니까?오른쪽 N은 체인 헤드 결점에서 링까지의 시작점을 나타내고, 왼쪽 L2는 만남점에서 링까지의 시작점을 나타내며, 왼쪽(x-1)(L1+L2)은 위에서 x-1바퀴를 돌려야 한다는 뜻이다.
그래서 결론은 우리가 먼저 8가지 방법을 통해 빠른 지침과 느린 지침의 만남점을 찾은 다음에 느린 지침이 만남점에서 움직이지 않고 빠른 지침이 체인 시계의 출발점으로 돌아오게 한 다음에 느린 지침을 함께 한 걸음 한 걸음 걷게 한다. 그들이 만났을 때 반드시 고리의 시작점에 있을 것이다.

ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        if(fast == NULL || fast->next == NULL) return NULL;
        fast = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }