C++LeetCode 구현(25.k 개 당 체인 시트 뒤 집기)

[LeetCode]25.Reverse Nodes in k-Group k 개 당 체인 시트 뒤 집기
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:

Only constant extra memory is allowed.

You may not alter the values in the list's nodes, only nodes itself may be changed.

이 문 제 는 우리 로 하여 금 각 k 개 를 한 조로 하여 체인 시 계 를 뒤 집 게 한다.실제 적 으로 원 체인 시 계 를 몇 개의 작은 부분 으로 나 눈 다음 에 각각 뒤 집 으 면 모두 두 개의 함수 가 필요 하 다.하 나 는 세그먼트 로 나 누 는 것 이 고 하 나 는 뒤 집 는 것 이다.문제 에서 준 예 를 들 어 주어진 링크 1->2->3->4->5 에 대해 일반적으로 링크 문 제 를 처리 할 때대부분 처음에 Dummy node 를 추가 합 니 다.링크 를 뒤 집 을 때 머리 결 점 이 변 할 수 있 기 때문에 현재 최신 머리 결 점 의 위 치 를 기록 하기 위해 도 입 된 Dummy node 는 Dummy node 를 추가 한 후 링크 를-1->1->2->3->4->5 로 바 꿉 니 다.k 가 3 이면 목 표 는 1,2,3 을 뒤 집 는 것 입 니 다.그러면 지침 이 필요 합 니 다.pre 와 next 는 각각 뒤 집 을 링크 의 앞 뒤 위 치 를 가리 키 고 뒤 집 은 pre 의 위 치 를 다음 과 같은 새로운 위치 로 업데이트 합 니 다.
-1->1->2->3->4->5
|        |  |
pre      cur next
-1->3->2->1->4->5
|     |  |
cur   pre next
이런 식 으로 보면 cur 가 k 개의 노드 를 지나 가면 next 는 cur->next 입 니 다.뒤 집기 함 수 를 호출 하여 부분 적 으로 뒤 집 을 수 있 습 니 다.뒤 집 힌 후에 새로운 cur 와 pre 의 위치 가 다 릅 니 다.그러면 뒤 집 힌 후에 cur 는 pre->next 로 업데이트 해 야 합 니 다.뒤 집 을 필요 가 없다 면 cur 는 cur->next 로 업데이트 되 고 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;
        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = head;
        dummy->next = head;
        for (int i = 1; cur; ++i) {
            if (i % k == 0) {
                pre = reverseOneGroup(pre, cur->next);
                cur = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
    ListNode* reverseOneGroup(ListNode* pre, ListNode* next) {
        ListNode *last = pre->next, *cur = last->next;
        while(cur != next) {
            last->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = last->next;
        }
        return last;
    }
};

우 리 는 한 함수 에서 완성 할 수 있 습 니 다.먼저 전체 링크 를 옮 겨 다 니 며 링크 의 길 이 를 통계 한 다음 에 길이 가 k 보다 크 면 교환 노드,k=2 일 때 각 단락 은 한 번 만 교환 해 야 합 니 다.k=3 일 때 각 단락 은 2 를 교환 해 야 합 니 다.그래서 i 는 1 부터 순환 하고 주 의 를 기울 여 한 단락 을 교환 한 후에 pre 지침 을 업데이트 한 다음 에 num 은 k 를 줄 이 고 num해법 2:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;
        dummy->next = head;
        int num = 0;
        while (cur = cur->next) ++num;
        while (num >= k) {
            cur = pre->next;
            for (int i = 1; i < k; ++i) {
                ListNode *t = cur->next;
                cur->next = t->next;
                t->next = pre->next;
                pre->next = t;
            }
            pre = cur;
            num -= k;
        }
        return dummy->next;
    }
};

우 리 는 또한 재 귀적 으로 할 수 있 습 니 다.헤드 로 각 단락 의 시작 위 치 를 기록 하고 cur 로 끝 위치의 다음 노드 를 기록 한 다음 에 reverse 함 수 를 호출 하여 이 단락 을 뒤 집 은 다음 에 new 를 얻 을 수 있 습 니 다.head,원래 의 head 는 끝 이 되 었 습 니 다.이때 뒤에 다음 단계 에서 얻 은 새로운 노드 를 재 귀적 으로 호출 하여 new 로 돌아 갑 니 다.head 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *cur = head;
        for (int i = 0; i < k; ++i) {
            if (!cur) return head;
            cur = cur->next;
        }
        ListNode *new_head = reverse(head, cur);
        head->next = reverseKGroup(cur, k);
        return new_head;
    }
    ListNode* reverse(ListNode* head, ListNode* tail) {
        ListNode *pre = tail;
        while (head != tail) {
            ListNode *t = head->next;
            head->next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }
};

C++구현 LeetCode(25.k 개 당 체인 시트 뒤 집기)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 k 개 당 체인 시트 뒤 집기 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부탁드립니다!