【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个结点反转单链表

关注我的微信公众号,回复“礼包”领取我的学习资料

涵盖自学编程、Java技术、分布式笔记、算法刷题和程序员必读电子书等众多资料合集。

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

原文 

https://segmentfault.com/a/1190000022346632

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 【Java 实现经典算法】每K个结点反转单链表

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址