LeetCode 25：Reverse Nodes in k-Group

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.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list’s nodes, only nodes itself may be changed.

传入一个链表，同时还传入一个参数k，从头到尾链表每k个节点进行颠倒顺序，最终尾部如果不满k个节点就不进行颠倒

这里最直接的方法就是将每K个数字倒序，然后连接起来

比如0~9，每组4个，那么first分别3->2->1->0，然后7->6->5->4，最后8->9；也就是先正序遍历K个节点，然后倒序生成新的链表，进而后面的放在next里，进行递归

大致可以得到这样一个流程图

利用栈的实现方法

package com.lihuia.leetcode25;

import java.util.Stack;

/**
 * Copyright (C), lihuia.com
 * FileName: Solution
 * Author:   lihui
 * Date:     2018/7/22
 */

public class Solution {
    
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode current = head;
        Stack<ListNode> stack = new Stack<ListNode>();
        
        for (int i = 0; i < k; i++) {
            if (head != null) {
                stack.push(head);
            } else {
                //不满K个
                return current;
            }
            head = head.next;
        }
        
        ListNode first = stack.pop();
        ListNode reverse = first;
        for (int i = 0; i < k - 1; i++) {
            first.next = stack.pop();
            first = first.next;
        }
        //后面每组倒序后新生成的链表，会接在当前该组的后方
        first.next = reverseKGroup(head, k);
        return reverse;
    }
}

比如有以下TestNG测试代码

package com.lihuia.leetcode25;

import javax.annotation.Resource;

import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * Copyright (C), lihuia.com
 * FileName: SolutionTest
 * Author:   lihui
 * Date:     2018/7/22
 */

public class SolutionTest {
    
    @Resource
    private ListNode head;
    private ListNode first;
    private Solution solution;
    private int maxLen = 10;
    private int k = 4;
    
    @BeforeClass
    public void beforeClass() {
        head = new ListNode(0);
        first = head;
        for (int i = 1; i < maxLen; i++) {
            head.next = new ListNode(i);
            head = head.next;
        }
        solution = new Solution();
    }
    
    @Test
    public void testReverseKGroup() {
        ListNode reverseListNode = solution.reverseKGroup(first, k);
        while (reverseListNode != null) {
            System.out.print(reverseListNode.val + " ");
            reverseListNode = reverseListNode.next;
        }
    }
}

第一轮：

首先遍历0->1->2->3四个节点，全部入栈，此时head指向了第二组4这个节点

first和reverse都指向3这个节点，接着reverse指向链表3->2->1->0，first指向了0这个节点

调用reverseKGroup进入递归

第二轮：

首先遍历4->5->6->7四个节点，全部入栈，此时head指向了第三组8这个节点

first和reverse都指向7这个节点，接着reverse指向链表7->6->5->4，first指向了4这个节点

调用reverseKGroup进入递归

第三轮：

首先遍历8->9两个节点，入栈之后，发现第三个元素为空，直接返回current，也就是未倒序的8->9

结果返回给第二轮的first.next=8->9，此时reverse为7->6->5->4->8->9

结果返回给第一轮的first.next=7->6->5->4->8->9，此时reverse为3->2->1->0->7->6->5->4->8->9

这样就完成了需求