全部文章

leetcode war 25 Reverse Nodes in k Group

2017-10-29 @sunderls

leetCode js

https://leetcode.com/problems/reverse-nodes-in-k-group/description/

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

analysis

we've done a special case(k = 2) in our last article leetcode war 24 - swap nodes in pairs, it cost us O(n) with three cursors.

for a general k, we can still accomplish it with a constant 3 cursor, like:

head -> 1 -> 2 -> 3 -> 4
head -> 3 -> 1 -> 2 -> 4
head -> 3 -> 2 -> 1 -> 4

but after iteration 2, we have to move p3(3) to 2, this needs a for loop, this accumulates to O(k2)

we can try another way

head -> 1 -> 2 -> 3 -> 4
head -> 2 -> 1 -> 3 -> 4
head -> 3 -> 2 -> 1 -> 4

which means we move p2 along the way, and swap p2.next with p1.next. and when p2 went after k - 1 round, update p1 to p2.

but the left-out nodes should remain as it is so we have to know where kth node is before setting p2 to the next

code

var reverseKGroup = function(head, k) {
    // fake head
    var start = new ListNode();
    start.next = head;

    // use some pointers
    var p1 = start;
    // pk is used to run ahead to determine whether start swapping
    var pk = p2 = p1.next;
    var p3 = null;
    var pknext = null;

    // a counter
    var count = k - 1;
    while (pk) {
        // first find the k-ahead node
        pknext = pk;
        count = k - 1;
        while (count > 0 && pknext) {
            pknext = pknext.next;
            count -= 1;
        }

        // if there is this node
        // safely do swapping for the next k - 1 round
        if (pknext) {
            count = k - 1;
            while (count > 0) {
                // swap p2.next with p1.next
                p3 = p2.next;
                p2.next = p3.next;
                p3.next = p1.next;
                p1.next = p3;
                count -= 1;
            }
            // after swaping reset all to next start line
            p1 = p2;
            pk = p2 = p2.next
        } else {
            break;
        }
    }

    return start.next;
};

It passed, ranking the top, fastest 119ms, wow!