C++LeetCode(143.링크 재 정렬)실현

[LeetCode]143.Reorder List 링크 정렬
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
이 링크 의 정렬 문 제 는 다음 과 같은 세 가지 작은 문제 로 나 눌 수 있다.
1.빠 르 고 느 린 지침 을 사용 하여 링크 의 중심 점 을 찾 고 링크 를 중심 점 에서 끊 어 두 개의 독립 된 링크 를 형성한다.
2.두 번 째 체인 을 뒤 집어 줍 니 다.
3.두 번 째 링크 의 요 소 를 첫 번 째 링크 에 간격 을 두 고 삽입 합 니 다.
해법 1:

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = NULL;
        ListNode *last = mid, *pre = NULL;
        while (last) {
            ListNode *next = last->next;
            last->next = pre;
            pre = last;
            last = next;
        }
        while (head && pre) {
            ListNode *next = head->next;
            head->next = pre;
            pre = pre->next;
            head->next->next = next;
            head = next;
        }
    }
};

우 리 는 쓰기 에 있어 서 간결 할 수 있 는 지 를 보 려 고 한다.위의 두 번 째 단 계 는 후반 부 링크 를 뒤 집 는 것 이다.그러면 우 리 는 스 택 의 후진 선 출 특성 을 빌려 할 수 있다.만약 에 우리 가 순서대로 모든 결산 점 을 스 택 에 누 르 면 스 택 을 나 갈 때 순 서 를 바 꿀 수 있 고 사실은 링크 를 뒤 집 는 것 과 같다.후반 부 체인 시 계 를 뒤 집 기만 하면 우 리 는 창고 결산 점 의 개 수 를 제어 해 야 하기 때문에 다행히 창고 에서 결산 점 의 개 수 를 직접 얻 을 수 있다.우 리 는 1 을 2 로 나 누 면 창고 결산 점 의 개 수 를 빼 야 한다.그 다음 에 우리 가 해 야 할 일 은 매번 에 스 택 에서 나 오 는 결산 점 을 정확 한 위치 에 삽입 하여 문제 에서 요구 하 는 순 서 를 만족 시 키 는 것 이다.링크 를 결산 점 에 삽입 하 는 작업 은 비교적 흔 하 다.여기 서 설명 을 많이 하지 않 고 마지막 으로 스 택 꼭대기 요소 뒤의 결산 점 을 끊 는 것 을 기억 하 는 것 이다.예 를 들 어 1->2->3->4.스 택 지붕 은 하나의 결산 점 4 만 나 면 된다.그 다음 에 원래 의 링크 를 넣 은 후에 1->4->2->3->(4)입 니 다.원래 의 링크 에서 3 점 을 찍 은 후에 결점 4 가 연결 되 어 있 기 때문에 우 리 는 결점 4 를 꺼 내 서 결점 1 과 2 사이 에 삽입 하지만 결점 3 뒤의 지침 은 결점 4 가 연결 되 어 있 기 때문에 우 리 는 이 연결 을 끊 어야 고리 가 나타 나 지 않 습 니 다.이때 결점 3 은 스 택 꼭대기 에 있 기 때 문 입 니 다.그래서 우 리 는 스 택 꼭대기 의 결산 점 을 직접 끊 으 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        stack<ListNode*> st;
        ListNode *cur = head;
        while (cur) {
            st.push(cur);
            cur = cur->next;
        }
        int cnt = ((int)st.size() - 1) / 2;
        cur = head;
        while (cnt-- > 0) {
            auto t = st.top(); st.pop();
            ListNode *next = cur->next;
            cur->next = t;
            t->next = next;
            cur = next;
        }
        st.top()->next = NULL;
    }
};

참고 자료:
https://leetcode.com/problems/reorder-list/
https://leetcode.com/problems/reorder-list/discuss/45175/Java-solution-with-stack
https://leetcode.com/problems/reorder-list/discuss/44992/Java-solution-with-3-steps
C++구현 LeetCode(143.링크 재 정렬)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 링크 재 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!