Recursive O(n) solution c++;


  • 0
    K

    Reverse the first K nodes and attach it to the reversed n-k node list.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
    
        ListNode *reverseLinkedList(ListNode *head)
        {
            ListNode* first = head;
            ListNode* second = head->next;
            first->next = NULL;
            while(second != NULL)
            {
                ListNode* third = second->next;
                second->next = first;
                first =second;
                second = third;
            }
            return first;
        }
        ListNode* reverseKGroup(ListNode* head, int k) {
            if(head==NULL)
            return head;
            ListNode* return_head = head;
            
            ListNode* after_k = head;
            int temp = k;
            while(temp>1)
            {
                
                after_k = after_k->next;
                if(after_k == NULL)
                return return_head;
                temp--;
            }
            ListNode *ndPart = after_k ->next;
            after_k->next = NULL;
            ListNode *reversed = reverseLinkedList(return_head);
            return_head = reversed;
            while(reversed->next !=NULL)
            {
                reversed = reversed->next;
            }
            reversed->next = reverseKGroup(ndPart,k);
            
            return return_head;
                
                
         
            
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.