第一行一个整数 n,n 表示单链表的节点数量。
第二行 n 个整数 val 表示链表的各个节点的值。
第三行一个整数 K。
在给定的函数内返回链表的头指针。
5 1 2 3 4 5 3
3 2 1 4 5
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int k = Integer.parseInt(br.readLine()); ListNode head = new ListNode(Integer.parseInt(strArr[0])); ListNode cur = head; for(int i = 1; i < strArr.length; i++){ cur.next = new ListNode(Integer.parseInt(strArr[i])); cur = cur.next; } head = reverseKGroups(head, k); while(head != null){ System.out.print(head.val + " "); head = head.next; } } private static ListNode reverseKGroups(ListNode head, int k) { ListNode cur = head; for(int i = 1; i < k && cur != null; i++) cur = cur.next; if(cur == null) return head; // 不足k个了,直接返回头节点 ListNode temp = cur.next; cur.next = null; ListNode newHead = reverseList(head); // 前面一段逆序 head.next = reverseKGroups(temp, k); // 后面继续进行k个一组的反转 return newHead; } private static ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode temp = cur.next; cur.next = prev; prev = cur; cur = temp; } return prev; } }
力扣上面的提交很快给结果通过,这个牛客判题系统,一会85%,再提交75%我都服了,并且判题时间很长,能不能把判题系统稍微做的好一点。
把我力扣写的题解复制过来,刷了十来道链表题了,基本上都能用递归写出来,之前是很害怕,感觉递归好难写。就遵循一句话就可以用递归都写出来。这句话分为三步
1、找到终止条件
2、假设递归函数已经将后面的都完成了
3、处理第一个情况。
在这个题目中是这么处理
1、递归终止条件是head为null或者剩余节点数量小于k,那就直接返回
2、如果链表为1->2->3->4->5->null,k为2,那么假设3->4->5经过递归函数以及完成了翻转
3、接下来处理第一个情况,也就是1->2。
import java.util.Scanner; /** * @Author fgf * @create 2020/3/5 12:44 * 将单链表的每K个节点之间逆序 */ class Node { public int val; public Node next; public Node(int data){ this.val = data; } } public class Main { public static Node reverseKGroup(Node head, int k){ if(head == null) return head; int m = k; ListNode cur = head; while(cur != null && --m >= 1) cur = cur.next; if(m >= 1) return head; //剩余节点不到k个,直接返回 ListNode pre = reverseKGroup(cur.next, k);//假设3->4->5->null已经完成,已经变成4->3->5->null cur.next = null; //处理第一种情况,当前节点为2,要把2的next设置为null,作为终止条件 cur = head;//从head也就是1开始处理 //将head到cur进行翻转 while(cur != null){ ListNode = cur.next; //记录下一个节点,也就是2 cur.next = pre;//将1指向pre也就是前一个节点,也就是前面的4->3->5->null pre = cur;//将pre设置为1 cur = next;//将cur设置为2 } return pre; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); Node head = new Node(-1); Node cur = head; for(int i=0; i<count; i++){ cur.next = new Node(scanner.nextInt()); cur = cur.next; } int k = scanner.nextInt(); Node result= reverseKGroup(head.next, k); while(result!=null){ System.out.print(result.val + " "); result = result.next; } } }