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;
        }

Log in to reply
 

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