【递归 分段反转链表，进行连接】 25 K个一组翻转链表

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5

思路

代码

public ListNode reverseKGroup(ListNode head, int k) { if(head==null||head.next==null) return head; ListNode tail = head; for(int i = 0;i<k;i++){ //剩余数量小于k，就返回这个链表的头结点 if(tail==null) return head; tail = tail.next; } //反转head-tail的元素，其中区间是左闭右开的,返回的是子链表的新头结点 ListNode prehead = reverse(head,tail); //当前的head在反转后成为最后一个元素，head的next等于下一个链表的头部 head.next = reverseKGroup (tail, k); //返回每一层的链表头部，头部在每次反转后成为尾部，与下一层递归的头部相连 return prehead; } //左闭右开 public ListNode reverse(ListNode head, ListNode tail){ ListNode pre = null; ListNode next = null; while(head!=tail){ //占下 next = head.next; //连接 head.next = pre; //两步移动 pre = head; head = next; } return pre; }