关于java:LeetCode刷题日记之K个一组翻转链表

明天刷到 LeetCode 第 25 题，记录一下刷题的思路，不便当前回看。（真的一周不写就容易忘啊，所以还是要多练）

这个题大略有三种解法：

借助栈先进后出的思路，当链表元素 k 个一组放进栈中，而后在拿进去。（毛病是工夫复杂度较高，入栈出栈都要遍历链表，不举荐，理解思路即可）。
递归：k 个一组进行递归，具体思路请参考前面图解。
迭代：同上，参考前面图解。

话不多说，先上代码：

        Deque<ListNode> stack = new LinkedList<>();

        ListNode dummy = new ListNode(0);
        // 这个 p 会始终挪动，须要另起一个指针
        ListNode p = dummy;
        while (true) {
            int count = 0;
            // 这儿不能间接 head 挪动，因为如果有余 k 个，head 指针将找不到，因而另起一个指针
            ListNode temp = head;
            // k 个一组放进栈中
            while (temp != null && count < k) {stack.push(temp);
                temp = temp.next;
                count++;
            }
            // 当有余 k 个不必反转
            if (count != k) {
                p.next = head;
                break;
            }
            while (!stack.isEmpty()) {p.next = stack.pop();
                p = p.next;
            }
            // 将 head 替换为 k 个地位之后，不便下次循环
            head = temp;
        }

        return dummy.next;

这个思路其实没啥好说的，用一个指针 p 顺次的跟着栈往后移，当有余 k 个时间接返回头指针 dummy.next。

这里须要强调的几点是在链表写代码时候的常识吧：

1、链表外面常常会有如下代码，初学者看着会很奇怪，我一开始学习的时候也纳闷了很久：

        ListNode dummy = new ListNode(0);
        ListNode p = dummy;

这里曾经新创建了一个 dummy，为啥还要再创立一个和 dummy 一样的 p？为啥不间接用 dummy?

起因是，当你新建的 dummy 节点在后续操作的时候，会进行挪动，如 p =p.next 这种，如果间接用 dummy 去操作，前面你拿到的 dummy 就不是原来的地位了，而是挪动后的地位，这时候如果你想要拿到原来的 dummy，就须要新创建一个帮手去帮 dummy 做这个事，也就是 p。

下面这个逻辑在链表代码外面会常常用到，搞懂其起因后在看代码就不会有种云里雾里的感觉了。

2、链表外面常常会呈现上面这种 xx.next 满天飞的状况，了解起来会很艰难。

head.next=next.next.next;
next.next=head;

你依照我的思路来想其实就会简略很多，当 xx.next 在表达式右边的时候，就只有一个含意，xx 的下一个节点指向表达式左边的地位。

如 head.next=next.next; 就是指 head 指向 next 的下一个节点。你这样去梳理下以前看着比拟懵逼的代码就会清晰很多。反正我思路是清晰很多。

3、一旦 A.next= B 之后，代表 A 以前指向的地位指针曾经断开，当初指向 B 了。如果后续还须要用以前 A.next 的节点话就须要提前记录下来。因而就会在链表了经常出现上面这种代码：

                ListNode next = tail.next.next;
                tail.next.next = prev.next;
                prev.next = tail.next;
                tail.next = next;

因为 tail.next.next 在第二行断开了，第四行有须要用到，所以会提前用 Next 把 tail.next.next 存起来。

第三点乍看和第一点很像，然而还是有轻微区别的，一个是指针挪动的记录，一个是指针断开的记录。

        int count = 0;
        ListNode curr = head;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count == k) {curr = reverseKGroup(curr, k);
            while (count-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }
            head = curr;
        }

        return head;

代码其实还是很清晰的，咱们一点一点来理一下。

        int count = 0;
        ListNode curr = head;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

下面这段代码的次要目标就是 k 个节点分组，这里 ListNode curr=head; 要用我下面的基本点想一下，因为如果间接用 head 后移的话初始的 head 地位就找不到了，因而须要一个帮手 curr 去帮它做这个事。

接着往下看，如果有 k 个节点，就 k 个一组翻转，否则间接返回。

curr = reverseKGroup(curr, k); 这个是递归调用，这里须要阐明的一点是在看递归相干代码不要强行去人肉递归，你会很苦楚的，且会把本人搞晕，毕竟咱们不是机器。咱们只须要晓得这个代码前面得出的后果就是通过 reverseKGroup(curr, k)这个函数解决的 curr 就间接是 k 个一组翻转好的后果，咱们当初惟一要做的就是，将 curr 后面的 k 个元素翻转好在组装就行。

而上面的代码就是做的这个事：

            while (count-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }
            head = curr;

这块不是那么好了解，碰到这种状况个别画个图，问题就迎刃而解了~

以 head = [1,2,3,4,5], k = 3 为例，图画的可能有点丑，然而可能会对你有点帮忙。

这里 k =3，因而只会循环三次，当最初循环完 curr 的地位是在头结点，head 的地位在 temp，因而前面须要将 head=curr。最初返回 head 即可。

        int n = 0;
//        统计链表长度
        for (ListNode i = head; i != null; n++, i = i.next);

        ListNode dmy = new ListNode(0);
        dmy.next = head;
        for(ListNode prev = dmy, tail = head; n >= k; n -= k) {for (int i = 1; i < k; i++) {
                ListNode next = tail.next.next;
                tail.next.next = prev.next;
                prev.next = tail.next;
                tail.next = next;
            }

            prev = tail;
            tail = tail.next;
        }
        return dmy.next;

迭代的代码可能会有点绕，xx.next.next 这种款式，不要有恐惧感，看懂之后思路还是很清晰的。

后面两行代码是用 n 统计链表长度。其中遍历链表的写法还是很新鲜的，值得借鉴。

上面在 head 后面结构了一个哨兵节点 dummy，而后以 dummy 为 prev,head 为 tail 就开始翻转了。

for(ListNode prev = dmy, tail = head; n >= k; n -= k)这块代码是将链表按 k 个一组开始进行翻转。

外面的 for (int i = 1; i < k; i++) 这里是从 1 开始而不是 0 开始，感觉会少循环一次。我是这么了解的，当有 k 个数，其实真正翻转的时候只会翻转 k - 1 次，这里 1 是没问题的。

具体的循环思路能够参考下图，画的有点乱，我置信你能看懂的~

一开始 prev 和 tail 是相邻的，tail.next.next=prev.next其实就是指将 tail 的下一个节点指向 prev 的下一个节点，留神是 tail 的下一个节点不是 tail。

而后 prev.next=tail.next 是指 prev 指向 tail 的下一个节点。

tail.next=next是指 tail 指向原来 tail.next.next 地位，这里不间接用 tail.next.next 是因为这个指针当初曾经断掉了，所以用实现保留好的 next。

在 k 个一组翻转完会将 prev 和 tail 进行从新赋值，在进行下一轮。

最初返回的是最开始的 head 节点地位，只是因为 head 当初曾经挪动不晓得到哪里去了，所以用的是 dummy.next，其实就是最开始的 head 地位。

这三个解法次要把握递归和迭代即可，栈那个其实没啥意义，工夫复杂度太高，理论很难用到，除非什么非凡场景。

迭代和递归写法其实都很绕，常常会呈现明天会写，过一周看又有点不会了，所以多看多写吧，没啥方法，加

关于java:LeetCode刷题日记之K个一组翻转链表

借助栈

看链表代码的几个重点思路

递归

迭代

写在最初