[LC 25]. Reverse Nodes in k-Group

对于LinkedList调换node顺序的问题,通常需要牵扯到previous, current, next三种类型的node,或者需要记录head在哪,以便最后返回。这类问题一个普遍的思路是加dummy node:


ListNode dummy = new ListNode(0);
dummy.next = head;

类似的问题还有[LC 24] swap pairs 和 [LC 61] rotate list。对[LC 61]来说,加dummy还有一个好处,就是不需要考虑k%len == 0, 即不需要rotate的情况。下面三行是rotate的code,顺序是不能变的,变了之后不保证k%len == 0的情况也对。

需要rotate的情况:0->1->2->3->null, k = 2, tail = 3, newtail = 2, dummy = 0.

tail.next = dummy.next; // 0, 3->1->2->3
dummy.next = newtail.next; // 0->3->1->2->3
newtail.next = null; // 0->3->1->2->null

不需要rotate的情况:0->1->2->null, k = 2, tail = newtail = 2, dummy = 0

tail.next = dummy.next; // 0, 2 -> 1 -> 2
dummy.next = newtail.next; // 0->1<->2
newtail.next = null; // 0->1->2->null

对于本题[LC 25],操作略复杂,容易不知所措。首先想到需要两个循环,外面的循环iterate over groups, 里面的循环reverse current group。对外面的循环,循环内部有两步,Step 1. 判断当前group是否完整;Step 2. reverse group。对于Step 1,容易搞不清现在是找到第k个还是第k-1个了,找一个小例子验证一下。对于Step 2,是进行的以下操作:

0(dummy)->1->2->3->next 变成 0->2->3->1->next, 变成0->3->2->1->next

即不断取出prev后面的node,插到tail的后面

        while (true) {
            // Step 1: is this group complete or ending early
            int count = k;
            while (count &gt; 0 &amp;&amp; tail != null) {
                count--;
                tail = tail.next;
            }
            if (tail == null) break; // reach the end 

            // Step 2: reverse group
            head = prev.next;
            while (prev.next != tail) {
                tmp = prev.next;
                prev.next = tmp.next;
                tmp.next = tail.next;
                tail.next = tmp;
            }

            prev = head;
            tail = head;
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s