Reverse Nodes in k-Group

Reverse Nodes in Pairs (LC.24)

Given a linked list, swap every two adjacent nodes and return its head.

Example

I: 1->2->3->4
O: 2->1->4->3

Analysis

Give a dummy head and write a swap next 2 helper.

Code

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;
    while (current != null) {
        current = swapNextPair(current);
    }
    return dummy.next;
}

// swap pair then return the start of next pair
// base -> a -> b -> c
private ListNode swapNextPair(ListNode base) {
    if (base.next == null || base.next.next == null) {
        return null; // no more pairs to swap
    }
    // swap
    ListNode a = base.next;
    ListNode b = base.next.next;
    ListNode c = base.next.next.next;
    base.next = b;
    b.next = a;
    a.next = c;    
    return a;
}

Reverse Nodes in k-Group (LC.25)

Given a linked list, reverse the list in a group of k nodes.

Assume k is a valid number. If the length of the leftover nodes is less than k, do nothing.

Example

I: 1->2->3->4->5
k = 2, O: 2->1->4->3->5
k = 3, O: 3->2->1->4->5

Approach

Step 1 Check the current group length >= k
Step 2 Reverse n_1 to n_k
Step 3 Set base.next to n_k and n_1.next to n_k+1

Code

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;
    while (current != null) {
        current = reverseNextGroup(current, k);
    }
    return dummy.next;
}

// base -> n_1 -> ... -> n_k -->n_k+1
private ListNode reverseNextGroup(ListNode base, int k) {
    ListNode travel = base.next;
    for (int i = 0; i < k; i++) {
        if (travel == null) return null;
        travel = travel.next;
    }
    // reverse
    ListNode current = base.next.next;
    ListNode prev = base.next;
    ListNode temp;
    while (k > 1 && current != null) {
        temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
        k--;
    }
    // connect
    ListNode newBase = base.next;
    base.next.next = current;
    base.next = prev;
    // return new base
    return newBase;
}