C++LeetCode 구현(86.링크 구분)

[LeetCode]86.Partition List 구분 링크
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
이 문 제 는 우리 에 게 링크 를 나 누 어 주어진 값 보다 작은 노드 를 모두 앞으로 옮 기 고 이 값 보다 큰 노드 의 순서 가 변 하지 않 으 며 부분 적 인 정렬 문제 에 해당 한다.그러면 생각 할 수 있 는 해법 은 먼저 주어진 값 보다 크 거나 같은 첫 번 째 노드 를 찾 는 것 이다.문제 에서 준 예 를 들 어 4 를 먼저 찾 은 다음 에 3 보다 작은 값 을 찾 는 것 이다.하 나 를 찾 을 때마다 이 를 4 전에 꺼 내 면 된다.코드 는 다음 과 같다.
해법

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;;
        while (pre->next && pre->next->val < x) pre = pre->next;
        cur = pre;
        while (cur->next) {
            if (cur->next->val < x) {
                ListNode *tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = pre->next;
                pre->next = tmp;
                pre = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

이러한 해법 의 링크 변화 순 서 는 다음 과 같다.
1 -> 4 -> 3 -> 2 -> 5 -> 2 
1 -> 2 -> 4 -> 3 -> 5 -> 2 
1 -> 2 -> 2 -> 4 -> 3 -> 5
이 문 제 는 주어진 값 보다 작은 모든 노드 를 꺼 내 새로운 링크 를 구성 하 는 해법 도 있다.이때 원 링크 에 남 은 노드 의 값 은 주어진 값 보다 크 거나 같 으 며 원 링크 를 새 링크 에 직접 연결 하면 된다.코드 는 다음 과 같다.
해법

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-1);
        ListNode *newDummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy, *p = newDummy;
        while (cur->next) {
            if (cur->next->val < x) {
                p->next = cur->next;
                p = p->next;
                cur->next = cur->next->next;
                p->next = NULL;
            } else {
                cur = cur->next;
            }
        }
        p->next = dummy->next;
        return newDummy->next;
    }
};

이 해법 링크 의 변화 순 서 는 다음 과 같 습 니 다.
Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2 
New:
Original: 4 -> 3 -> 2 -> 5 -> 2 
New:　  1
Original: 4 -> 3 -> 5 -> 2 
New:　  1 -> 2
Original: 4 -> 3 -> 5 
New:　  1 -> 2 -> 2
Original: 
New:　  1 -> 2 -> 2 -> 4 -> 3 -> 5 
C++구현 LeetCode(86.링크 구분)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 링크 구분 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!