Share my Java Solution with comments in line


  • 56
    R
      public class Solution {
            public ListNode reverseKGroup(ListNode head, int k) {
                if (head==null||head.next==null||k<2) return head;
        
                ListNode dummy = new ListNode(0);
                dummy.next = head;
                
                ListNode tail = dummy, prev = dummy,temp;
                int count;
                while(true){
                    count =k;
                    while(count>0&&tail!=null){
                        count--;
                        tail=tail.next;
                    } 
                    if (tail==null) break;//Has reached the end
                    
        
                    head=prev.next;//for next cycle
                // prev-->temp-->...--->....--->tail-->....
                // Delete @temp and insert to the next position of @tail
                // prev-->...-->...-->tail-->head-->...
                // Assign @temp to the next node of @prev
                // prev-->temp-->...-->tail-->...-->...
                // Keep doing until @tail is the next node of @prev
                    while(prev.next!=tail){
                        temp=prev.next;//Assign
                        prev.next=temp.next;//Delete
                        
                        temp.next=tail.next;
                        tail.next=temp;//Insert
                        
                    }
                    
                    tail=head;
                    prev=head;
                    
                }
                return dummy.next;
                
            }
        }

  • -2
    Z

    Doesn't the line "head=prev.next;//for next cycle" should be "head=tail.next;" ?


  • 3
    D

    Nice way of reverse a linked list, though I am more used to do it in the old way: keep reverse the direction of link from start to end.


  • 0
    A

    @zilchistdeepblue no because after the adjustment the original pre.next will be at the position of the original tail, which will grantee the program to enter the next cycle.


  • 0

    smart. using tail as a segment stop is so convenient.


  • 0
    H

    @zilchistdeepblue It's right because current prev.next will be the head of the next cyle


  • 1

    Count the length of Link List, for every sub-list length as k, do reverse.

        public ListNode reverseKGroup(ListNode head, int k) {
          int n = 0;
          ListNode cur = head;
          while(cur != null){
            cur = cur.next;
            n++;
          }
          ListNode dmy = new ListNode(0);
          dmy.next = head;
          ListNode s = dmy, e = dmy.next; //s: start, e: end
          for(int i = n; i >= k; i -= k){
            for(int j = 1; j < k; j++){ // reverse group
              ListNode next = e.next;
              e.next = next.next;
              next.next = s.next;
              s.next = next;
            }
            s = e;
            e = s.next;
          }
          return dmy.next;
        }

  • 1
    M

    Similar idea to yours with explanation.

    For example,

    list = 1 -> 2 -> 3 -> 4 -> 5, k = 3
    
    1. Use a dummy head to simplify operations.
    Dummy -> 1 -> 2 -> 3 -> 4 -> 5
    
    1. Use three pointers. The operation is similar to Leetcode#92 Reverse Linked List II.
    • The pointer n will go k steps further.
      (If there are no k nodes further, it means we don't have to reverse these k nodes. ==> Stop. )
    • The pointer p is always at the fixed position in this for-loop.
    • The pointer c = p.next, which means the current node we want to move.
    • The pointer start means the starting node for the next loop.
    Dummy -> 1 -> 2 -> 3 -> 4 -> 5
       p     c         n
             start
    
    Dummy -> 2 -> 3 -> 1 -> 4 -> 5
       p     c    n    start
    
    Dummy -> 3 -> 2 -> 1 -> 4 -> 5
       p     c         start
             n
    
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy = new ListNode(0), start = dummy;
            dummy.next = head;
            while(true) {
                ListNode p = start, c, n = p;
                start = p.next;
                for(int i = 0; i < k && n != null; i++) n = n.next;
                if(n == null) break;
                for(int i = 0; i < k-1; i++) {
                    c = p.next;
                    p.next = c.next;
                    c.next = n.next;
                    n.next = c;
                }
            }
            return dummy.next;
        }
    }
    

Log in to reply
 

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