題目描述：

給你一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表。

k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。

如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(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)交換。

思路分析：

步驟分解:

• 鏈表分區(qū)為已翻轉(zhuǎn)部分+待翻轉(zhuǎn)部分+未翻轉(zhuǎn)部分
• 每次翻轉(zhuǎn)前，要確定翻轉(zhuǎn)鏈表的范圍，這個(gè)必須通過(guò) k 此循環(huán)來(lái)確定
• 需記錄翻轉(zhuǎn)鏈表前驅(qū)和后繼，方便翻轉(zhuǎn)完成后把已翻轉(zhuǎn)部分和未翻轉(zhuǎn)部分連接起來(lái)
• 初始需要兩個(gè)變量 pre 和 end，pre 代表待翻轉(zhuǎn)鏈表的前驅(qū)，end 代表待翻轉(zhuǎn)鏈表的末尾
• 經(jīng)過(guò)k此循環(huán)，end 到達(dá)末尾，記錄待翻轉(zhuǎn)鏈表的后繼 next = end.next
• 翻轉(zhuǎn)鏈表，然后將三部分鏈表連接起來(lái)，然后重置 pre 和 end 指針，然后進(jìn)入下一次循環(huán)
• 特殊情況，當(dāng)翻轉(zhuǎn)部分長(zhǎng)度不足 k 時(shí)，在定位 end 完成后，end==null，已經(jīng)到達(dá)末尾，說(shuō)明題目已完成，直接返回即可

時(shí)間復(fù)雜度為 O(n*K)， 最好的情況為 O(n)， 最差的情況未 O(n^2)O
空間復(fù)雜度為 O(1)，除了幾個(gè)必須的節(jié)點(diǎn)指針外，我們并沒(méi)有占用其他空間。

 

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k 
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 說(shuō)明剩下的鏈表不夠k個(gè),跳出循環(huán)
            if count : 
                p.next = head
                break
            # 翻轉(zhuǎn)操作
            while stack:
                p.next = stack.pop()
                p = p.next
            #與剩下鏈表連接起來(lái) 
            p.next = tmp
            head = tmp
        
        return dummy.next

java實(shí)現(xiàn)：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null){
            return head;
        }
        //定義一個(gè)假的節(jié)點(diǎn)。
        ListNode dummy=new ListNode(0);
        //假節(jié)點(diǎn)的next指向head。
        // dummy->1->2->3->4->5
        dummy.next=head;
        //初始化pre和end都指向dummy。pre指每次要翻轉(zhuǎn)的鏈表的頭結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。end指每次要翻轉(zhuǎn)的鏈表的尾節(jié)點(diǎn)
        ListNode pre=dummy;
        ListNode end=dummy;

        while(end.next!=null){
            //循環(huán)k次，找到需要翻轉(zhuǎn)的鏈表的結(jié)尾,這里每次循環(huán)要判斷end是否等于空,因?yàn)槿绻麨榭?，end.next會(huì)報(bào)空指針異常。
            //dummy->1->2->3->4->5 若k為2，循環(huán)2次，end指向2
            for(int i=0;i                end=end.next;
            }
            //如果end==null，即需要翻轉(zhuǎn)的鏈表的節(jié)點(diǎn)數(shù)小于k，不執(zhí)行翻轉(zhuǎn)。
            if(end==null){
                break;
            }
            //先記錄下end.next,方便后面鏈接鏈表
            ListNode next=end.next;
            //然后斷開鏈表
            end.next=null;
            //記錄下要翻轉(zhuǎn)鏈表的頭節(jié)點(diǎn)
            ListNode start=pre.next;
            //翻轉(zhuǎn)鏈表,pre.next指向翻轉(zhuǎn)后的鏈表。1->2 變成2->1。dummy->2->1
            pre.next=reverse(start);
            //翻轉(zhuǎn)后頭節(jié)點(diǎn)變到最后。通過(guò).next把斷開的鏈表重新鏈接。
            start.next=next;
            //將pre換成下次要翻轉(zhuǎn)的鏈表的頭結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。即start
            pre=start;
            //翻轉(zhuǎn)結(jié)束，將end置為下次要翻轉(zhuǎn)的鏈表的頭結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。即start
            end=start;
        }
        return dummy.next;


    }
    //鏈表翻轉(zhuǎn)
    // 例子：   head：1->2->3->4
    public ListNode reverse(ListNode head) {
         //單鏈表為空或只有一個(gè)節(jié)點(diǎn)，直接返回原單鏈表
        if (head == null || head.next == null){
            return head;
        }
        //前一個(gè)節(jié)點(diǎn)指針
        ListNode preNode = null;
        //當(dāng)前節(jié)點(diǎn)指針
        ListNode curNode = head;
        //下一個(gè)節(jié)點(diǎn)指針
        ListNode nextNode = null;
        while (curNode != null){
            nextNode = curNode.next;//nextNode 指向下一個(gè)節(jié)點(diǎn),保存當(dāng)前節(jié)點(diǎn)后面的鏈表。
            curNode.next=preNode;//將當(dāng)前節(jié)點(diǎn)next域指向前一個(gè)節(jié)點(diǎn)   null<-1<-2<-3<-4
            preNode = curNode;//preNode 指針向后移動(dòng)。preNode指向當(dāng)前節(jié)點(diǎn)。
            curNode = nextNode;//curNode指針向后移動(dòng)。下一個(gè)節(jié)點(diǎn)變成當(dāng)前節(jié)點(diǎn)
        }
        return preNode;

    }


}