1 ms Java Clean Iterative Solution based on Slicing


  • 0
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        private ListNode reverseNodes(ListNode prevNode, ListNode startNode, ListNode endNode, ListNode nextNode) {
                ListNode p1, p2, p3;
                p1 = startNode;
                p2 = p1.next;
                p3 = p2.next;
                
                prevNode.next = endNode;
                startNode.next = nextNode;
                
                while(p3 != nextNode) {
                    p2.next = p1;
                    
                    p1 = p2;
                    p2 = p3;
                    p3 = p3.next;
                }
                
                p2.next = p1;
                
                return startNode;
        }
        
    
        public ListNode reverseKGroup(ListNode head, int k) {
            if(null == head || k == 1) {
                return head;
            }
            
            ListNode prevNode, startNode, endNode, nextNode, result;
    
            prevNode = new ListNode(0);
            prevNode.next = head;
            result = prevNode;
    
            startNode = head;
            endNode = head;
            
            int steps = 1;
            boolean modified = false;
    
            while(null != endNode && null != startNode) {
                endNode = endNode.next;
                ++steps;
                
                if(null != endNode && steps == k) {
                    modified = true;
                    steps = 1;
                    nextNode = endNode.next;
    
                    prevNode = reverseNodes(prevNode, startNode, endNode, nextNode);
    
                    startNode = prevNode.next;
                    endNode = prevNode.next;
                }
            }
            
            if(modified)
                return result.next;
            
            return head;
        }
    }
    

Log in to reply
 

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