Concise solution on reverse list in k-Group solution in Java and C++


  • 0
    Y

    The idea of this solution is reverse sublist one by one iteratively. Every time return new head, then go to next sublist. Reverse function is a generalized version of 206, reverse a single list.

    class Solution {
        public:
            ListNode* reverseKGroup(ListNode* head, int k) {
                ListNode dummy(0);
                dummy.next = head;
                ListNode* p1 = &dummy, *p2 = p1->next;
                int counter = k;
                while (p2 != nullptr){
                    p2 = p2->next;counter--;
                    if (counter == 0){
                        ListNode* next_p1 = p1->next;
                        /*reverse 2 endpoints, the sublist k is [next_p1, p2)*/
                        p1->next = reverse(next_p1, p2);
                        p1 = next_p1;
                        counter = k;
                    }
                }
                return dummy.next;
            }
        private:
            ListNode* reverse (ListNode* head, ListNode* tail){
                if (head == tail || head->next == tail) 
                    return head;
                ListNode* p1=head->next, *p2 = p1;
                head->next = tail;
                while (p1!= tail){
                    p2= p2->next; p1->next=head; head = p1; p1=p2;
                }
                return head;
            }
    };
    

    Java:

    public class Solution {
    
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode p1=dummy, p2=p1.next;
            int counter = k;
            while (p2 != null){
                p2=p2.next; counter--;
                if (counter == 0){
                    counter = k;
                    ListNode nextP1 = p1.next;
                    /* reverse sub k list [nextP1, p2)*/
                    p1.next = reverse(nextP1, p2);
                    p1 = nextP1; //Note: dont change p2 since is always the next sublist's begin
                }
            }
            return dummy.next;
        }
        
        private ListNode reverse(ListNode head, ListNode tail){
            if (head == tail || head.next == tail) 
                return head;
            ListNode p1 = head.next, p2 = p1;
            head.next = tail;
            while (p1 != tail){
                p2 = p1.next; p1.next = head; head = p1; p1 = p2;
            }
            return head;
        }
    }
    

Log in to reply
 

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