乘风破浪：LeetCode真题_025_Reverse Nodes in k-Group

一、前言

将一个链表按照一定的长度切成几部分，然后每部分进行翻转以后再拼接成一个链表是比较困难的，但是这也能锻炼我们的思维能力。

二、Reverse Nodes in k-Group

2.1 问题

2.2 分析与解决

最简单的想法，我们可以将链表分成几部分，每一个部分分开考虑，比如使用头插法，正好可以将顺序颠倒一下，或者我们通过某种方式使得顺序发生改变，然后再结合起来。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode dom = new ListNode(0);
        dom.next = head;
        ListNode tmp = head;
        int size = 0;

        //获取队列长度
        //get list size
        while (tmp != null) {
            tmp = tmp.next;
            size++;
        }

        //如果长度不够,则直接返回
        if (size < k) return head;

        //切割数组,并转换
        //split list, and reverse sub list
        int position = 0;
        ListNode pre = dom;
        ListNode rHead = null;
        ListNode rTail = null;
        ListNode next = null;
        for (int count = 0; (count + 1) * k <= size; count++) {

            position = 0;

            rHead = null;
            rTail = null;
            tmp = pre.next;
            //翻转子队列
            //reverse sub list
            while (position < k) {

                next = tmp.next;

                if (rTail == null) {
                    rHead = tmp;
                    rTail = tmp;
                } else {
                    tmp.next = rHead;
                    rHead = tmp;
                }

                tmp = next;
                position++;
            }

            if (rHead != null) {
                pre.next = rHead;//这一步第一次就将头指针赋值给了dom.next，这样完成了衔接和搭配
                rTail.next = tmp;
                pre = rTail;
            }
        }

        return dom.next;
    }
}

在我们的程序中,如下面的代码其实就是头插法的实现。

1    if (rTail == null) {
2          rHead = tmp;
3          rTail = tmp;
4    } else {
5          tmp.next = rHead;
6          rHead = tmp;
7    }

通过上面的图，我们可以更加清楚地明白程序的内容。

三、总结

在处理这样的问题的时候，我们一定要画图，通过图中指针的变化，我们可以很容易、很准确的写出代码。另外也要注意头插法对于链表排序的作用，当然尾插法也是我们最常用的方式。