LeetCode - K个一组翻转链表

晓痴

发布于 2019-07-24 11:55:21

4490

发布于 2019-07-24 11:55:21

文章被收录于专栏：曌的晓痴

该题是四周前做的一道题目，当时写这题时刚好写了前面一题（之后会发出来），然后题目刚好是类似的，只需要稍微换个思路就可以了。这题的难度是困难，真的是为数不多的写出来的困难级别的....

原题地址： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

题目描述：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这题的一个关键点在于，使用栈去做一个ListNode的存储，保证刚好K个时可以去实现翻转。

新建一个pre用于表示当前翻转的链表的前置，h表示当前的头部
遍历列表，遍历一个，就把该节点放入Stack中，然后计数
当计数达到K个时，说明该翻转了，于是就从Stack中不停的获取最后一个，将pre指针指到当前的翻转过的最后一个元素，h为头部。
如果计数达不到K，说明已经没有更多的ListNode了，这个时候，就可以直接从Stack中取出元素，执行翻转操作。

最后，返回h这个链表的头部即可。

中文官网题解：

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

个人题解：

/**
 * 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) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        Deque<ListNode> stack = new ArrayDeque<>(k);
        ListNode pre = null;
        ListNode h = null;
        while (head != null) {
            int count = 0;
            while (count < k && head != null) {
                count++;
                stack.addLast(head);
                head = head.next;
            }
            if (count == k) {
                if (pre == null) {
                    pre = stack.removeLast();
                    h = pre;
                }
                while (!stack.isEmpty()) {
                    pre.next = stack.removeLast();
                    pre = pre.next;
                }
            } else {
                if (pre == null) {
                    pre = stack.pop();
                    h = pre;
                }
                while (!stack.isEmpty()) {
                    pre.next = stack.pop();
                    pre = pre.next;
                }
            }
            pre.next = null;
        }
        return h;
    }
}

结果：

......（贴上自己的代码的运行结果）