這篇文章主要介紹了C++如何實現(xiàn)每k個一組翻轉(zhuǎn)鏈表的相關(guān)知識，內(nèi)容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++如何實現(xiàn)每k個一組翻轉(zhuǎn)鏈表文章都會有所收獲，下面我們一起來看看吧。

創(chuàng)新互聯(lián)專注于從江網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供從江營銷型網(wǎng)站建設(shè)，從江網(wǎng)站制作、從江網(wǎng)頁設(shè)計、從江網(wǎng)站官網(wǎng)定制、微信小程序定制開發(fā)服務(wù)，打造從江網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供從江網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

每k個一組翻轉(zhuǎn)鏈表

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個為一組來翻轉(zhuǎn)鏈表，實際上是把原鏈表分成若干小段，然后分別對其進行翻轉(zhuǎn)，那么肯定總共需要兩個函數(shù)，一個是用來分段的，一個是用來翻轉(zhuǎn)的，以題目中給的例子來看，對于給定鏈表 1->2->3->4->5，一般在處理鏈表問題時，大多時候都會在開頭再加一個 dummy node，因為翻轉(zhuǎn)鏈表時頭結(jié)點可能會變化，為了記錄當(dāng)前最新的頭結(jié)點的位置而引入的 dummy node，加入 dummy node 后的鏈表變?yōu)?-1->1->2->3->4->5，如果k為3的話，目標是將 1,2,3 翻轉(zhuǎn)一下，那么需要一些指針，pre 和 next 分別指向要翻轉(zhuǎn)的鏈表的前后的位置，然后翻轉(zhuǎn)后 pre 的位置更新到如下新的位置：

-1->1->2->3->4->5
|        |  |
pre      cur next

-1->3->2->1->4->5
|     |  |
cur   pre next

以此類推，只要 cur 走過k個節(jié)點，那么 next 就是 cur->next，就可以調(diào)用翻轉(zhuǎn)函數(shù)來進行局部翻轉(zhuǎn)了，注意翻轉(zhuǎn)之后新的 cur 和 pre 的位置都不同了，那么翻轉(zhuǎn)之后，cur 應(yīng)該更新為 pre->next，而如果不需要翻轉(zhuǎn)的話，cur 更新為 cur->next，代碼如下所示：

解法一：

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;
    }
};

我們也可以在一個函數(shù)中完成，首先遍歷整個鏈表，統(tǒng)計出鏈表的長度，然后如果長度大于等于k，交換節(jié)點，當(dāng) k=2 時，每段只需要交換一次，當(dāng) k=3 時，每段需要交換2此，所以i從1開始循環(huán)，注意交換一段后更新 pre 指針，然后 num 自減k，直到 num<k 時循環(huán)結(jié)束，參見代碼如下：

解法二：

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;
    }
};

我們也可以使用遞歸來做，用 head 記錄每段的開始位置，cur 記錄結(jié)束位置的下一個節(jié)點，然后調(diào)用 reverse 函數(shù)來將這段翻轉(zhuǎn)，然后得到一個 new_head，原來的 head 就變成了末尾，這時候后面接上遞歸調(diào)用下一段得到的新節(jié)點，返回 new_head 即可，參見代碼如下：

解法三：

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;
    }
};

關(guān)于“C++如何實現(xiàn)每k個一組翻轉(zhuǎn)鏈表”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“C++如何實現(xiàn)每k個一組翻轉(zhuǎn)鏈表”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

本文名稱：C++如何實現(xiàn)每k個一組翻轉(zhuǎn)鏈表
網(wǎng)站URL：http://www.chinadenli.net/article40/gpoheo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、網(wǎng)站設(shè)計公司、Google、網(wǎng)站營銷、域名注冊、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)