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.

reverse_node_k_group.py

#!/usr/bin/env python3


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


class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None or k < 2:
            return head
        
        p = s = ListNode(0)
        l = k
        p.next = head
        head = p

        while s is not None and k != 0:
            s = s.next
            k -= 1

        while s is not None:
            p, s = self.reverse(p, s)
            k = l
            while s is not None and k != 0:
                s = s.next
                k -= 1
        
        return head.next

    def reverse(self, p: ListNode, s: ListNode) -> tuple:
        prev = p.next
        tail = p.next
        tmp = p.next
        flag = s.next

        p.next = None
        while prev is not flag:
            tmp = p.next
            p.next = prev
            prev = prev.next
            p.next.next = tmp
        
        tail.next = prev
        p = tail
        s = tail
        return p, s


def main():
    head = ListNode(1)
    tmp = head
    for i in range(2, 6):
        ne = ListNode(i)
        tmp.next = ne
        tmp = ne
    print(Solution().reverseKGroup(head, 2).val)
    

if __name__ == '__main__':
    main()

reverseNodeKGroup.c

//
//  main.c
//  reverse node in k group
//
//  Created by fzw on 10/12/18.
//  Copyright © 2018 n. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode * next;
};

struct ListNode * reverseKGroup(struct ListNode * head, int k);
void reverse(struct ListNode ** p, struct ListNode ** s);

int main(int argc, const char * argv[]) {
    struct ListNode l5 = {.val=5, .next=NULL};
    struct ListNode l4 = {.val=4, .next=&l5};
    struct ListNode l3 = {.val=3, .next=&l4};
    struct ListNode l2 = {.val=2, .next=&l3};
    struct ListNode l1 = {.val=1, .next=&l2};
    reverseKGroup(&l1, 3);
    return 0;
}

struct ListNode * reverseKGroup(struct ListNode * head, int k) {
    if (!head || !head->next || k < 2) {
        return head;
    }
    
    struct ListNode *s, *p = (struct ListNode *)malloc(sizeof(struct ListNode));
    int len = k;
    p->next = head;
    head = p;
    s = p;
    
    while (k-- && s != NULL) {
        s = s->next;
    }
    while (s!=NULL) {
        reverse(&p, &s);
        k = len;
        while (k-- && s!=NULL) {
            s = s->next;
        }
    }
    return head->next;
}

void reverse(struct ListNode ** p, struct ListNode ** s) {
    struct ListNode * prev = (*p)->next, * tmp, * tail = (*p)->next, * flag = (*s)->next;
    (*p)->next = NULL;
    while (prev!=flag) {
        tmp = (*p)->next;
        (*p)->next = prev;
        prev = prev->next;
        (*p)->next->next = tmp;
    }
    
    tail->next = prev;
    *p = tail;
    *s = tail;
}