LeetCode.jpg

目錄鏈接：http://www.reibang.com/p/9c0ada9e0ede

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

給出一個(gè)鏈表限煞，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，并返回翻轉(zhuǎn)后的鏈表。

k 是一個(gè)正整數(shù)怀喉，它的值小于或等于鏈表的長(zhǎng)度吹菱。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么將最后剩余節(jié)點(diǎn)保持原有順序忧风。

示例 :

給定這個(gè)鏈表：1->2->3->4->5

當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: 2->1->4->3->5

當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5

說(shuō)明 :

你的算法只能使用常數(shù)的額外空間掺冠。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換码党。

切題

一德崭、Clarification

1斥黑、每組k個(gè)元素翻轉(zhuǎn)后，每組之間的銜接眉厨。[1,k] 與 [k+1,2k]之間銜接

2锌奴、注意 剩余元素的處理

二、Possible Solution

1憾股、迭代

遍歷鏈表 找出每組的 首尾以及下一組的首鹿蜀，借助單鏈表翻轉(zhuǎn)獲得翻轉(zhuǎn)后的首尾，對(duì)首尾節(jié)點(diǎn)銜接處理服球，對(duì)哨兵節(jié)點(diǎn)移位處理

時(shí)間復(fù)雜度 O(N)

2茴恰、遞歸

遞歸終止條件：

剩余節(jié)點(diǎn) < k

遞歸從里向外出來(lái)，每層遞歸返回當(dāng)前層級(jí)鏈表翻轉(zhuǎn)后的頭節(jié)點(diǎn)有咨，那么每層遞歸中我們知道當(dāng)前層級(jí)翻轉(zhuǎn)后的頭尾節(jié)點(diǎn)以及下一個(gè)k元素組的頭節(jié)點(diǎn)（遞歸的上一層級(jí)）琐簇，可以很輕松地將翻轉(zhuǎn)后的鏈表銜接起來(lái)

3、借助棧

將k個(gè)元素壓入棧座享，通過(guò)出棧翻轉(zhuǎn)婉商，注意剩余元素處理

Python3實(shí)現(xiàn)

迭代 借助單鏈表翻轉(zhuǎn)

# @author:leacoder
# @des: 迭代 借助單鏈表翻轉(zhuǎn)  k個(gè)一組翻轉(zhuǎn)鏈表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        cur = head #由于遍歷
        dim = ListNode(0) #新建一節(jié)點(diǎn) 
        dim.next = head #next指向head
        pre = dim #pre 賦值為 dim  1、記錄和獲取 k個(gè)一組的頭 2渣叛、方便統(tǒng)一處理
        # pre 與 dim 均為哨兵
        count = 1
        while cur: #遍歷鏈表
            if count % k == 0: #k個(gè)一組 對(duì)這里面的數(shù)據(jù)翻轉(zhuǎn)
                nextstart = cur.next #記錄 后一個(gè) k個(gè)一組的 頭節(jié)點(diǎn)
                cur.next = None #賦值為None 前面 k個(gè)一組數(shù)據(jù) 為新的鏈表 以 None結(jié)束 這個(gè)新鏈表可以采用206的處理方式
                end, start = self.reverse(pre.next)  #翻轉(zhuǎn)新鏈表 返回翻轉(zhuǎn)的  尾 和 頭  注pre.next 為新鏈表翻轉(zhuǎn)前的頭
                # 銜接處理丈秩，哨兵的next指向翻轉(zhuǎn)后的頭， 翻轉(zhuǎn)后的尾的next指向nextstart
                # pre 和 cur 依次下移k個(gè)元素 變?yōu)?end 和 nextstart下一輪處理就變成本輪一樣了
                pre.next,end.next,pre,cur = start,nextstart,end,nextstart
            else:
                cur = cur.next #我們關(guān)心k個(gè)一組的首尾
            count += 1
        return dim.next
    
    def reverse(self, head): #翻轉(zhuǎn)鏈表
        dim1,cur,pre = head,head,None
        while cur: #遍歷
            cur.next,pre,cur  = pre,cur,cur.next
        return dim1,pre    #翻轉(zhuǎn)后end 和 start

遞歸

# @author:leacoder
# @des: 遞歸  k個(gè)一組翻轉(zhuǎn)鏈表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
       
        if self.isEnd(head,k):
            return head
        pre = ListNode(None) # 哨兵
        pre.next,cur,count =  head,head,1  

        while count <= k: # 翻轉(zhuǎn) k個(gè)元素鏈表  處理類(lèi)似 206
            cur.next,pre,cur,count  = pre,cur,cur.next,count + 1 
        # 循環(huán)結(jié)束后 cur 指向 下一組 k個(gè)元素(未翻轉(zhuǎn))的頭 ;pre指向當(dāng)前組在翻轉(zhuǎn)后的頭節(jié)點(diǎn)
        nexthead = self.reverseKGroup(cur,k) # nexthead 下一組翻轉(zhuǎn)后的頭節(jié)點(diǎn)

        head.next = nexthead #當(dāng)前組的head在翻轉(zhuǎn)后成為尾節(jié)點(diǎn)淳衙，其next指向nexthead 下一組翻轉(zhuǎn)后的頭節(jié)點(diǎn)
        return pre  # 返回 翻轉(zhuǎn)后的頭節(jié)點(diǎn)

    # 遞歸終止判斷：
    def isEnd(self,head,k):
        count,cur = 0,head
        while cur:
            count = count + 1
            cur = cur.next
            if count >= k:
                return False # 
        return True

借助棧

# @author:leacoder
# @des: 借助棧  k個(gè)一組翻轉(zhuǎn)鏈表
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        result= ListNode(None)
        cur,result.next = head,head
        tmpresult = result
        stack = [] # 列表實(shí)現(xiàn)棧的 先入后出功能
        count = 0

        while cur:
            count = count + 1
            stack.append(cur) # 入棧
            cur = cur.next
            if count % k == 0: # 已存儲(chǔ)k個(gè)元素
                count = 0
                while stack: # 出棧倒換
                    tmpresult.next = stack.pop()
                    tmpresult = tmpresult.next

        # 處理 stack 中剩余元素
        while stack:
            tmpresult.next = stack.pop(0) # 
            tmpresult = tmpresult.next 
        return result.next

C++實(shí)現(xiàn)

存儲(chǔ)法

用數(shù)組存儲(chǔ)k個(gè)元素蘑秽，雖然能通過(guò)但是執(zhí)行用時(shí)有點(diǎn)長(zhǎng)，不過(guò)邏輯簡(jiǎn)單

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * @author:leacoder
 * @des: 存儲(chǔ)法 k個(gè)一組翻轉(zhuǎn)鏈表
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *nodearray[k];//存儲(chǔ) 需翻轉(zhuǎn)的 k個(gè)節(jié)點(diǎn)
        ListNode* result = new ListNode(0); //翻轉(zhuǎn)后鏈表 用于結(jié)果返回
        ListNode* ret = result;//由于存儲(chǔ)翻轉(zhuǎn)后鏈表
        int count = 0;
        while( NULL != head){
            ListNode* next = head->next; //記錄下移節(jié)點(diǎn)
            nodearray[count] = head; //記錄到數(shù)組
            count++;//數(shù)組 下標(biāo)自加 
            if(k == count){ //已存 k個(gè)值  需要翻轉(zhuǎn)了
               for(int i = k;i>0;i--){ //循環(huán)讀取 數(shù)組中數(shù)據(jù)
                   ret->next = nodearray[i-1]; //從后往前去數(shù)組中數(shù)據(jù) 添加到ret鏈表中
                   ret = ret->next;//移位
                   nodearray[i-1] = NULL;//置空
                   count--;//數(shù)組中數(shù)據(jù)個(gè)數(shù)--
               }
            }
            head = next;
        }
        
        for(int i = 0;i<count;i++){//處理不需要翻轉(zhuǎn)的數(shù)據(jù)
           ret->next = nodearray[i];
           ret = ret->next;
           nodearray[i] = NULL;
        }
        ret->next = NULL;
        return result->next;
    }
};

k作為函數(shù)參數(shù)傳入后就確定了可以當(dāng)做常數(shù)箫攀，但是k作為參數(shù)可以為合理范圍內(nèi)任意值不確定肠牲，這點(diǎn)和題目描述說(shuō)明貌似有點(diǎn)出入
說(shuō)明 : 你的算法只能使用常數(shù)的額外空間。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值靴跛，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換缀雳。

我這種方法處理也只是提供一種思路，待后續(xù)其他實(shí)現(xiàn)方法

GitHub鏈接：
https://github.com/lichangke/LeetCode

知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/

簡(jiǎn)書(shū)個(gè)人首頁(yè)：
http://www.reibang.com/u/3e95c7555dc7

個(gè)人Blog:
https://lichangke.github.io/

歡迎大家來(lái)一起交流學(xué)習(xí)