题目描述

  • 给定一个常数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中各个链表连接

代码

  1. package com.liuyong666.pat;
  3. import java.util.ArrayList;
  4. import java.util.List;
  6. public class Main {
  7.     static class ListNode{
  8.         int val;
  9.         ListNode next = null;
  10.         public ListNode(int val){
  11.             this.val = val;
  12.         }
  13.     }
  14.     public static ListNode reversePartNode(ListNode head, int k){
  16.         if(head == null || k < 1){
  17.             return null;
  18.         }
  20.         ListNode p = head;
  21.         //获取链表长度
  22.         int len = 0;
  23.         while(p != null){
  24.             len++;
  25.             p = p.next;
  26.         }
  28.         ListNode reverseListHead = null;
  29.         ListNode curNode = head;
  30.         ListNode preNode = null;
  31.         ListNode nextNode = null;
  32.         //List存放各链表头结点
  33.         List<ListNode> list = new ArrayList<ListNode>();
  35.         //count 计数器 记录k个元素，每k个重新置1
  36.         int count = 1;
  37.         //需要发生反转的结点个数
  38.         int reverseNum = (len / k) * k;
  39.         while(curNode != null){
  41.             nextNode = curNode.next;
  43.             if( count <= k){
  45.                 if(count == k){
  47.                     reverseListHead = curNode;
  48.                     list.add(reverseListHead);
  49.                     count = 1;
  51.                     curNode.next = preNode;
  52.                     preNode = null;
  53.                     curNode = nextNode;
  54.                 }else{
  55.                     count++;
  57.                     curNode.next = preNode;
  58.                     preNode = curNode;
  59.                     curNode = nextNode;
  60.                 }
  61.             }
  63.             if(reverseNum == 1 && count != k){
  64.                 list.add(curNode);
  65.                 break;
  66.             }
  68.             reverseNum--;
  70.         }
  71.         ListNode newHead = list.get(0);
  73.         for(int i = 0; i < list.size() - 1; i++){
  74.             p = list.get(i);
  75.             while(p.next != null){
  76.                 p = p.next;
  77.             }
  78.             p.next = list.get(i + 1);
  80.         }
  82.         return newHead;
  83.     }
  84. }
  85. public static void main(String[] args) {
  86.     ListNode node1 = new ListNode(1);
  87.     ListNode node2 = new ListNode(2);
  88.     ListNode node3 = new ListNode(3);
  89.     ListNode node4 = new ListNode(4);
  90.     ListNode node5 = new ListNode(5);
  91.     ListNode node6 = new ListNode(6);
  92.     node1.next = node2;
  93.     node2.next = node3;
  94.     node3.next = node4;
  95.     node4.next = node5;
  96.     node5.next = node6;
  97.     ListNode p = node1;
  98.     while(p != null){
  99.         System.out.print(p.val+" ");
  100.         p = p.next;
  101.     }
  102.     System.out.println();
  104.     ListNode revNode = reversePartNode(node1, 4);
  105.     while(revNode != null){
  106.         System.out.print(revNode.val+" ");
  107.         revNode = revNode.next;
  108.     }
  110.     }