25. Reverse Nodes in k-Group

三刷
Version #3 Pure Iteration
比version2要好很多了，没有while(true)这种有毒的写法
以前一直写半recursion半iterative的方法，今天直接懵逼了忘了recursion的怎么写，就写了一个纯iteration的方法
基本来说就是把整个list看成两个level
每个level都是完全的reverse
底层是数出k个来，reverse
高层是k个为一组，组与组之间reverse
Bug
自己一个坑就是 最后return null
但是当面对 k = 1以及 “1, 2” k = 2 这样的例子的时候
最后都是跳不进
if (nextHead == null) {
      return dummy.next;
}
这里面的
所以最后的最后统一都return dummy.next
其实想了想还不如写成
if (nextHead == null) {
    currHead = null;
    break;
}
Time O(2k) Space O(1)

99.97 %

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode currPrev = dummy;
ListNode currHead = head;
ListNode currTail = null;
ListNode nextHead = null;
while (currHead != null) {
currTail = currHead;
nextHead = currTail.next;
for (int i = 0; i < k - 1; i++) {
if (nextHead == null) {
return dummy.next;
}
currTail = currTail.next;
nextHead = currTail.next;
}
reverse(currHead, nextHead);

currPrev.next = currTail;
currPrev = currHead;
currHead.next = nextHead;
currHead = nextHead;
}
return dummy.next;
}

private void reverse(ListNode currHead, ListNode nextHead) {
ListNode prev = null;
ListNode curr = currHead;
ListNode next = null;
while (curr != nextHead) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
}
}


二刷
Recursion
99.98 %

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return head;
        ListNode curr = head;
        ListNode prev = null;
        // If the remain list is not long enough for reverse k, just return the original sequence
        int count = k;
        while (count-- > 0 && curr != null) {
            prev = curr;
            curr = curr.next;
        }
        if (count >= 0) {
            return head;
        } else {
            reverseInterval(head, prev);
            head.next = reverseKGroup(curr, k);
            return prev;
        }
    }
    private void reverseInterval(ListNode start, ListNode end) {
        ListNode prev = null;
        ListNode curr = start;
        ListNode next = null;
        while (curr != end) {
            next = curr.next;     
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        curr.next = prev;
    }
 
}


Version #1 Recursion
这里有一个技术性的问题。。。
在LeetCode上第一遍跑的时候最后一个tesecase TLE了
然而第二次跑就AC了，而且也没有特别慢，beats 57.62%

不懂是个什么情况

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        //n1 n2 n3 ... nk nkp
        //n1.next = reverseKGroup(nkp, k)
        //return nk
        ListNode n1 = head;
        ListNode nk = n1;
        ListNode nkplus = n1;
        int index = 1;
        for (; index <= k; index++) {
            if (nkplus == null) {
                break;
            }
            nk = nkplus;
            nkplus = nkplus.next;
        }
        if (index != k + 1) {
            return head;
        } else {
            reverseKNodes(n1, nk);
            n1.next = reverseKGroup(nkplus, k);
            return nk;
        }
    }
     private void reverseKNodes(ListNode head, ListNode tail) {
            //      1  ->  2  ->  3
            //     head          tail
            //                   pre   curr   next
       
            ListNode pre = null;
            ListNode curr = head;
            ListNode next = null;
            while(pre != tail) {
                next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
        }
}

Versiont #2 Non-recursion
7.49%
比较慢但是感觉比较直观
public class Solution {
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // Write your code here
        if (head == null || head.next == null || k <= 0) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (true) {
            ListNode newHead = reverseNextK(curr, k);
            if (newHead == null) break;
            prev.next = newHead;
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }
    //n1 .... nk, nk+ 1
    private ListNode reverseNextK(ListNode head, int k) {
        if (head == null) return null;
        ListNode n1 = head;
        ListNode curr = n1;
        ListNode nk, nkp;
        while (k > 1) {
            curr = curr.next;
            if (curr == null) return null;
            k--;
        }
        nk = curr;
        nkp = nk.next;
        curr = n1;
        ListNode prev = null;
        ListNode next = null;
        while (curr != nkp) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        n1.next = nkp;
        return nk;
    }
}