no dummy nodes -- break down into simple methods -- 1. find end node, 2. reverse and 3. adjust links


  • 0
    V
    public class Solution {
        public ListNode fhead = null;
        public int count = 0;
        public ListNode ReverseKGroup(ListNode head, int k) {
            if (head == null) return head;
            ListNode start = head; ListNode end = head;
            
            end = GetEnd(start, k); //find end node.
            if(end == null && count < k) return head; //k too large to reverse
            var ret = Reverse(start, end);
            fhead = ret[0];
            start = end;
    
            while (end != null) {
                end = GetEnd(start, k);
                if (end == null && count < k) break; // k too large for remaining nodes
                var _ret = Reverse(start, end);
                ret[1].next = _ret[0];
                ret = _ret;
                start = end;
            }
            
            ret[1].next = start;
            return fhead;
        }
        
        // simple method to get the End node determined by given K
       // given 1->2->3 and k = 2, this method returns node '3'
        public ListNode GetEnd(ListNode s, int k) {
            ListNode e = s; count = 0;
            while (e != null) {
                count++;
                e = e.next;
                if (count == k) {
                    break;
                }
            }
            return e;
        }
        
        // Rerverses the list specified by start and end and then returns both start and end of reversed list
        public ListNode[] Reverse(ListNode start, ListNode end) {
            ListNode p = start;
            ListNode temp = null;
    
            while (p != end) {
                ListNode q = p.next;
                p.next = temp;
                temp = p;
                p = q;
            }
    
            return new ListNode[2] { temp, start }; // return new start and end after reversing
        }  
    }
    
    

Log in to reply
 

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