转载

【Java 实现经典算法】每K个结点反转单链表

题目描述

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。
例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；
如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。

思路

通过链表长度和K值确定需要反转的结点数
每K个反转成新链表，把头保存到List中
需要反转的结点数已到并且剩下的结点数不足K个，不反转，即把当前结点存到List中
把List中各个链表连接

代码

package com.liuyong666.pat; import java.util.ArrayList; import java.util.List; public class Main { static class ListNode{ int val; ListNode next = null; public ListNode(int val){ this.val = val; } } public static ListNode reversePartNode(ListNode head, int k){ if(head == null || k < 1){ return null; } ListNode p = head; //获取链表长度 int len = 0; while(p != null){ len++; p = p.next; } ListNode reverseListHead = null; ListNode curNode = head; ListNode preNode = null; ListNode nextNode = null; //List存放各链表头结点 List<ListNode> list = new ArrayList<ListNode>(); //count 计数器记录k个元素，每k个重新置1 int count = 1; //需要发生反转的结点个数 int reverseNum = (len / k) * k; while(curNode != null){ nextNode = curNode.next; if( count <= k){ if(count == k){ reverseListHead = curNode; list.add(reverseListHead); count = 1; curNode.next = preNode; preNode = null; curNode = nextNode; }else{ count++; curNode.next = preNode; preNode = curNode; curNode = nextNode; } } if(reverseNum == 1 && count != k){ list.add(curNode); break; } reverseNum--; } ListNode newHead = list.get(0); for(int i = 0; i < list.size() - 1; i++){ p = list.get(i); while(p.next != null){ p = p.next; } p.next = list.get(i + 1); } return newHead; } } public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); ListNode node6 = new ListNode(6); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; ListNode p = node1; while(p != null){ System.out.print(p.val+" "); p = p.next; } System.out.println(); ListNode revNode = reversePartNode(node1, 4); while(revNode != null){ System.out.print(revNode.val+" "); revNode = revNode.next; } }

我组建了一个技术交流群，提供免费的每日科技早报服务，里边也会有众多知名互联网企业的技术大佬一起交流学习，共同成长。需要的朋友可以加我微信（微信ID：919201148），我拉你进群，并有福利相送。

【Java 实现经典算法】每K个结点反转单链表