[leetcode] 25. Reverse Nodes in k-Group

문제

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 kthen left-out nodes in the end should remain as it is.

 

풀이

list 문제의 연속이다.

전체 길이를 구한다음 k개씩 묶어서 각각을 뒤집는다. 뒤집는 과정은 다음과 같다.

 

Time Complexity : $O(n)$

 

코드

/**
 * 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(head==NULL || k==1)return head;
        ListNode* prev = new ListNode(0);
        prev->next = head;
        
        int l=0;
        for(ListNode* it = head; it!=NULL; it=it->next)l++;
        
        ListNode *p = prev;
        for(int i=0;i+k<=l;i+=k)
        {
            ListNode* now = p->next;
            ListNode* nxt = now->next;
            for(int j=1;j<k;j++)
            {
                now->next= nxt->next;
                nxt->next =p->next;
                p->next = nxt;
                nxt =now->next;
            }
            p=now;
        }
        return prev->next;
    }
};