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个结点）注意要处理特殊情况，例如给定的列表为空怎么办，初试链表的结点数小于k怎么办等等 package com.Hard.Ryan; public class ReverseNodesinkGroup { public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public static void main(String[] args) { ReverseNodesinkGroup rNodesinkGroup = new ReverseNodesinkGroup(); ListNode l1 = new ListNode(1); l1.next = new ListNode(2); l1.next.next = new ListNode(3); l1.next.next.next = new ListNode(4); l1.next.next.next.next = new ListNode(5); ListNode l2 = rNodesinkGroup.reverseKGroup(l1, 2); while (l2 != null) { System.out.print(l2.val + " "); l2 = l2.next; } } public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next=head; ListNode lastNode = head; ListNode subListNodes = head; ListNode newhNode=head; ListNode subreverlast=dummy; ListNode restNodes=dummy; if (head==null) { return head; } for (int i = 1; i < k; i++) { newhNode = newhNode.next; if (newhNode==null) { System.out.println(1); return head; } } while (subListNodes != null) { int i = 1; for (i = 1; i < k && lastNode.next != null; i++) { lastNode = lastNode.next; } System.out.println("lastnode:"+lastNode.val); if (i<k&&lastNode.next == null) { subreverlast.next=restNodes; break; } restNodes=lastNode.next; lastNode.next = null; System.out.println("subreverlast:"+subreverlast.val); subreverlast.next = reverselist(subListNodes); while (subreverlast.next!= null) { subreverlast = subreverlast.next; } System.out.println("subreverlast:"+subreverlast.val); System.out.println("restNodes:"+restNodes.val); subListNodes=restNodes; lastNode=restNodes; } return newhNode; } public ListNode reverselist(ListNode l1) { if (l1 == null || l1.next == null) { return l1; } ListNode reverHead = reverselist(l1.next); l1.next.next = l1; l1.next = null; return reverHead; } }

最后附上大神的代码，巨简洁

public ListNode reverseKGroup(ListNode head, int k) { ListNode curr = head; int count = 0; while (curr != null && count != k) { // find the k+1 node curr = curr.next; count++; } if (count == k) { // if k+1 node is found curr = reverseKGroup(curr, k); // reverse list with k+1 node as head // head - head-pointer to direct part, // curr - head-pointer to reversed part; while (count-- > 0) { // reverse current k-group: ListNode tmp = head.next; // tmp - next head in direct part head.next = curr; // preappending "direct" head to the reversed list curr = head; // move head of reversed part to a new node head = tmp; // move "direct" head to the next node in direct part } head = curr; } return head; }