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


一个linkedlist里面,k个k个node进行reverse,最后剩余的不足k个的nodes保留原样。

整个reverse过程中需要记录的是:就是要想清楚在reverse的过程中怎么把他们都记录下来并且完成所需的连接。。。

  • 当前k-group之前的k-group经过reverse之后的的tail
  • 当前k-group 之后的k-group经过翻转之后的head
  • 所以当翻转完当前k-group之后可以与前后接上。
Recursive:
public ListNode reverseKGroup(ListNode head, int k) {
//用指针的原因是:当当前head到tail之间的nodes数目小于k的时候,
就不需要翻转,直接返回head      
        ListNode cur = head;
        int count = 0;
        while (cur != null && count != k){
            cur = cur.next;
            count ++;
        }
        if (count == k){//是一个完整的k-group
//最终可知返回的cur是下一个k-group reverseKGroup处理完之后的head
//当前k-group的head.next应该指向cur,所以cur相当于一个pre指针了
            cur = reverseKGroup(cur, k);
            while (k > 0){
                ListNode next = head.next;
                head.next = cur;
                cur = head;
                head = next;
                k --;
            }
            head = cur;
//这里因为最后是返回head的,所以把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

Iterative:
public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null 
|| k == 1) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
//start指向dummy是为了翻转第一组:第一组的start就是dummy
//由于start是exclusive的
        ListNode start = dummy;
        int count = 0;
        while (head != null){
            count ++;//count在之间++
            if (count % k == 0){
//当进入到这个if里面的时候,head是当前k-group中的最后一个元素
//由于end也是exlusive的,所以传入head.next
//返回的node是当前k-group reverse之后的tail,所以它同时也是下一个group的
exclusive的start,所以把它赋给start
                start = reverse(start, head.next);
                head = start.next;//同时继续进行while loop
            }else {
                head = head.next;
            }
        }
        return dummy.next;
    }
//reverse一个k-group的nodes
//start为前一个k-group的tail,所以也为当前k-group的start(exclusive)
//end为后一个k-group的start,所以也为当前k-group的end(exclusive)
//返回当前k-group reverse后的tail
    public ListNode reverse(ListNode start, ListNode end){
        ListNode cur = start.next; //cur放到k-group的头准备开始遍历
//此时未翻转的k-group的头将会是翻转之后最终的尾,需要记录它用来返回        
        ListNode tail = cur; 
        ListNode pre = start;
        while (cur != end){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }//reverse k-group结束:此时:
        //cur在end的位置,pre是k-group的新的头
        start.next = pre;//把前一个k-group的尾和当前k-group的头相连
        tail.next = end;//把当前k-group的尾和下一个k-group的头相连。
在没有进行这步之前,当前k-group的尾是和前k-group的尾相连的
        return tail;//返回当前k-group的尾
    }
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: