Java easy understand solution with constant space


  • 0
    A
     public ListNode reverseKGroup(ListNode head, int k) {
    
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;// 0->1->2->3->4->5
        ListNode pre = dummyNode;
        ListNode curr = head;
        ListNode tail = head;
        //Now it became: (pre)0->(head,tail)1->2->3->4->5
        //The solution is find next K nodes, reverse them, 
        //then after the first loop, tail->dummyNode->pre; dummyNode.next is the new head;
        //then tail point to the first node of next K nodes.
        //find next K nodes, do the reverse again. 
        //If head==null, return. 
    
        boolean getOut = false;
        while (true) {
         //find next K nodes. if null, return. 
          for (int i = 0; i < k; i++) {
            if (head != null) {
              head = head.next;
            } else {
              getOut = true;
              break;
            }
          }
    
          if (getOut)
            break;
         // Reverse k nodes.
          for (int i = 0; i < k; i++) {
            ListNode tmp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = tmp;
          }
          tail.next.next = pre;
          pre = tail;
          tail.next = head;
          tail = head;
        }
        return dummyNode.next;
      }
    

Log in to reply
 

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