Easiest to Understand, extremely intutive


  • 0
    K

    public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

    if (head == null || head.next == null || k == 0)
    {
        return head;
    }
    // Create dummy nodes and point them to head.
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode orignaldummy = dummy;
    
    // This is the count of swaps that will reverse a list. 1->2 to 2->1 is order of 2 so count starts at 1.
    int count = 1; 
    
    ListNode p1 = head;
    
    int length = 1;
    //Find the length of list.
    while (p1.next != null)
    {
        p1 = p1.next;
        length++;
    }
    
    p1 = head;
    
    // imagine list 1->2->3->4->5. it has length of 5. if k = 2 then only two reversals are possible. the last 5 remains untouched. so 5/2 = 2 (int).
    
    int totalReversalsPossible = length/k;
    int currentReversalsCount = 0;
    // while 0 < 2
    while (currentReversalsCount < totalReversalsPossible)
    {
        //while 1 < 2
        while (count < k)
        {
            ListNode p2 = p1.next;
            p1.next = p1.next.next;
            p2.next = dummy.next;
            dummy.next = p2;
            count++;
        }
        // move everything up by 1.
        dummy = p1;
        p1 = p1.next;
        count = 1;
        currentReversalsCount++;
    }
    //return orignal dummy.next which is head.
    return orignaldummy.next;
    }
    

    }

    O(n) time and O(1) space.

    Let me know if i can optimize it somehow


Log in to reply
 

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