LeetCode25.k個一組翻轉連結清單

題目來源：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/description/

題目描述：

該題目是對反轉一個連結清單的更新版。

如何反轉一個連結清單我在之前的部落格已經寫了：https://blog.csdn.net/qq_39241239/article/details/82973024

算法描述：

1.判斷連結清單，若連結清單為空或k=1直接傳回head。

2.每k個結點周遊連結清單。相當于把一個大連結清單分成k個結點為連結清單的小連結清單。

3.讓每個連結清單都進行反轉，最後再把這些連結清單連接配接起來就可以了。

代碼如下：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* p = head;  
        ListNode* r; 
        //若連結清單為空或k=1直接傳回head
        if(!p || k == 1) 
            return p;  
        for(int i = 1; i < k; i ++){
            //若剩餘結點不夠k個則直接傳回head
            if(!p->next)    
                return head;
            p = p->next;
        }
        //p，r為分界線，p為前面需要倒置的連結清單的最後一個結點，r為進入遞歸的第一個節點（head）
        r = p->next;
        //截取連結清單
        p->next = NULL;
        //temp為倒置後的連結清單
        ListNode* temp = reverse(head);
        ListNode* newHead = temp;
        //找到連結清單最後
        while(temp->next){
            temp= temp->next;
        }
        //在連結清單最後遞歸拼接需要倒置的其他連結清單
        temp->next = reverseKGroup(r,k);
        return newHead;
    }
    //反轉連結清單方法
    ListNode* reverse(ListNode* head) {
        ListNode *p,*newHead=NULL;
       	while(head){
       		p=head;
       		head=head->next;
       		p->next=newHead;
       		newHead=p;
		}
        return newHead;
    }
};
           

Java代碼：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        ListNode check =head;
        int canProceed = 0;
        int count = 0;
        
        while(canProceed<k && check != null){
            check=check.next;
            canProceed++;
        }
        
        if(canProceed==k){
            while(count<k && cur != null){
                next = cur.next;
                cur.next=prev;
                prev=cur;
                cur=next;
                count++;
            }
            if(next!=null){
                head.next=reverseKGroup(next,k);
            }
            return prev;
        } else {
            return head;
        }
    }
}