Most concise Java O(n) Solution with explanation


  • 1

    In order to solve this one, we can simply repeat three steps:

    • 1 Find the node: Pre which is before the nodes we want to reverse.

    • 2 Check if there are k nodes after Pre. If there are not we can stop.

    • 3 Reverse the k nodes after Pre.

    It's very easy, right?

    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head==null || k<2)  return head;
            
            ListNode fakeHead = new ListNode(9);
            ListNode pre = fakeHead;
            pre.next = head;
            
            while(hasKMoreNodes(pre,k)){
                ListNode first = pre.next;
                for(int i=0;i<k-1;++i){
                    ListNode next = first.next;
                    first.next = next.next;
                    next.next = pre.next;
                    pre.next = next;
                }
                pre = first;
            }
            
            return fakeHead.next;
        }
        
        public boolean hasKMoreNodes(ListNode pre, int k){
            ListNode cur = pre;
            for(int i=0;i<k;++i){
                cur = cur.next;
                if(cur==null) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.