Reverse Nodes in k-Group

Leave a comment

September 18, 2016 by oneOokay

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.

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-group经过reverse之后的的tail
  • 当前k-group 之后的k-group经过翻转之后的head
  • 所以当翻转完当前k-group之后可以与前后接上。
public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        while (cur != null && count != k){
            cur =;
            count ++;
        if (count == k){//是一个完整的k-group
//最终可知返回的cur是下一个k-group reverseKGroup处理完之后的head
            cur = reverseKGroup(cur, k);
            while (k > 0){
                ListNode next =;
       = cur;
                cur = head;
                head = next;
                k --;
            head = cur;
//当前cur的位置就是当前k-group reverse完之后的头。
        return head;//如果没有翻转,直接返回head。

Iterative的话:ListNode reverse(ListNode start, ListNode end): reverse start和end之间的nodes(不包含start和end)返回翻转之后的tail,作为下一group的start

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || == null 
|| k == 1) return head;
        ListNode dummy = new ListNode(-1); = head;
        ListNode start = dummy;
        int count = 0;
        while (head != null){
            count ++;//count在之间++
            if (count % k == 0){
//返回的node是当前k-group reverse之后的tail,所以它同时也是下一个group的
                start = reverse(start,;
                head =;//同时继续进行while loop
            }else {
                head =;
//返回当前k-group reverse后的tail
    public ListNode reverse(ListNode start, ListNode end){
        ListNode cur =; //cur放到k-group的头准备开始遍历
        ListNode tail = cur; 
        ListNode pre = start;
        while (cur != end){
            ListNode next =;
   = pre;
            pre = cur;
            cur = next;
        }//reverse k-group结束:此时:
        //cur在end的位置,pre是k-group的新的头 = pre;//把前一个k-group的尾和当前k-group的头相连 = end;//把当前k-group的尾和下一个k-group的头相连。
        return tail;//返回当前k-group的尾

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: