25. K 个一组翻转链表
给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
示例 1:
![](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg)
输入:head = [1,2,3,4,5], k = 2 输出:[2,1,4,3,5]
示例 2:
输入:head = [1,2,3,4,5], k = 3 输出:[3,2,1,4,5]
提示:
- 链表中的节点数目为
n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
解决思路:按块翻转,注意保存关键位置和切分
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1,head); // 前一部分已经反转的节点链表 ListNode pre = dummy; // 每次反转部分的尾节点 ListNode end = dummy; while (end.next != null) { for (int i = 0; i < k && end != null; i++) end = end.next; if (end == null) break; //已经反转链表的下一位置即为本次翻转的起始位置 ListNode start = pre.next; //保存之后链表的位置,反转后进行连接 ListNode next = end.next; //切割 end.next = null; //反转并链接前半部分 pre.next = reverse(start); //链接后半部分 start.next = next; //更新下标 pre = start; end = pre; } return dummy.next; } public ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
标签:pre,25,ListNode,val,next,链表,end,翻转 From: https://www.cnblogs.com/fulaien/p/17287231.html