Leetcode: 25. Reverse Nodes in k-Group

Description

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.

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

Only constant memory is allowed.

Example

For 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

思路

• k-group反轉
• 首先寫一個單鏈表反轉函數，指定頭結點和尾節點，然後再函數中反轉鏈表
• 從給定鏈表頭開始，每次讀取k個長度的鏈表，調用反轉函數，然後再繼續這個過程
• 註意考慮兩個反轉鏈表之間的連接時候的情況

• 代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k == 1) return head;
        
        ListNode *res = NULL, *ptr = NULL, *cur = NULL, *pre = NULL;
        while(head){
            int count = k;
            ptr = NULL;
            cur = head;
            //while實現每次截取k個長度的鏈表
            while(head){
                if(ptr == NULL)
                    ptr = head;
                    
                cur = head;
                head = head->next;
                count--;
                if(count == 0) break;
            }
            
            //此時需要反轉
            if(count == 0 && cur && ptr){
                Reverse(&ptr, &cur);
            } 
            
            //連接兩個反轉部分或不反轉部分
            if(!pre){
                pre = cur;
            }
            else{
                pre->next = ptr;
                pre = cur;
            }
         
            //記錄反轉鏈表的頭節點
            if(!res) res = ptr;
            
            //特殊情況考慮，即剛好反轉到鏈表末尾
            if(!head && count == 0) pre->next = NULL;
        }
        
        return res;
    }
    
    //反轉單鏈表
    void Reverse(ListNode **head, ListNode **tail){
        ListNode *end = *tail, *cur = *head, *ptr = NULL, *tmp = NULL;
       
        ptr = cur->next; 
        *tail = cur;
        while(ptr != end){
            tmp = ptr->next;
            ptr->next = cur;
            cur = ptr;
            ptr = tmp;
        }
        
        if(ptr != end)
            end->next = ptr;
        else
            end->next = cur;
           
        *head = end;
    }
};