LeetCode 25:Reverse Nodes in k-Group

作者: LiHui 分类: LeetCode 发布时间: 2018-07-21 00:15

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里,进行递归

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

NewImage

利用栈的实现方法

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

这样就完成了需求

纯属恶搞

浙ICP备16024533号

浙公网安备 33010802007459号