welcome to my blog
LeetCode Top 100 Liked Questions 25. Reverse Nodes in k-Group (Java版; Hard)
题目描述
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.Example:Given this linked list: 1->2->3->4->5For k = 2, you should return: 2->1->4->3->5For k = 3, you should return: 3->2->1->4->5Note:Only constant extra memory is allowed.You may not alter the values in the list's nodes, only nodes itself may be changed.
第一次做; 递归, 核心是递归函数逻辑: 从head开始, 反转k个节点, 和下一段拼接好(这句话里面隐藏的新条件新递归), 最后返回头结点
//这道题很递归; 每一段的处理方式都一样, 但是怎么写呢? 递归函数逻辑是什么?class Solution { //递归函数逻辑: 从head开始, 反转k个节点, 和下一段拼接好(这句话里面隐藏的新条件新递归), 最后返回头结点 public ListNode reverseKGroup(ListNode head, int k) { //base case if(head==null || head.next==null || k<=1) return head; // //判断是否有k个节点 int n = 0; ListNode cur=head; while(cur!=null){ n++; if(n==k) break; cur = cur.next; } //如果不足k个节点, 则不用翻转, 直接返回头结点 if(n<k) return head; //长度够k, 反转链表 //先保存下一段待反转链表的头结点 ListNode nextHead = cur.next; ListNode left=null, right; cur = head; for(int i=0; i<k; i++){ //save next right = cur.next; //change cur.next = left; //update left = cur; cur = right; } //反转后的链表的尾巴连接下一段待反转链表反转后的新头 head.next = reverseKGroup(nextHead, k); //返回当前段的头 return left; }}
第一次做; 创建dummy节点, 这样就不用单独处理一次了; 简洁些
class Solution { public ListNode reverseKGroup(ListNode head, int k) { //input check if(head==null || head.next == null || k<=1) return head; //创建dummy节点; 将dummy节点当成已处理的节点 ListNode dummy = new ListNode(0); dummy.next = head; //需要知道上一段反转过后的尾巴,下一段待反转链表的头 ListNode preHead = dummy, preTail = dummy, nextHead = head; while(nextHead!=null){ //准备反转nextHead开始的一段链表 ListNode cur = nextHead; //检查长度是否不小于k int n = 0; while(cur!=null){ cur = cur.next; n++; if(n==k) break; } //如果长度小于k, 就不用反转了 if(n<k) break; //长度不小于k, 进行反转操作 ListNode left=null, right; cur = nextHead; for(int i=0; i<k; i++){ //save next right = cur.next; //change cur.next = left; //update left = cur; cur = right; } //update //上一段的尾巴连接当前段的头 preTail.next = left; preTail = nextHead; nextHead = cur; //细节: 暂时连起来, 如果跳出循环就不用单独再连一次了 preTail.next = nextHead; } return dummy.next; }}
第一次做; 画图; 先单独处理一次, 再用循环处理剩下的部分; 写的稍有些啰嗦, 尤其是需要单独处理一次
class Solution { public ListNode reverseKGroup(ListNode head, int k) { //input check if(head==null || head.next==null) return head; //统计链表长度 int n=0; ListNode cur=head; while(cur!=null){ n++; cur = cur.next; } if(n<k) return head; //反转的次数 int times = n/k; //先单独反转一次 ListNode[] res = reverse(head, k); //最终需要返回的头部 ListNode newHead = res[0]; ListNode tail = res[1]; ListNode nextHead = res[2]; //处理剩余的部分 for(int i=1; i<times; i++){ ListNode[] tmp = reverse(nextHead, k); //老尾巴连接新头 tail.next = tmp[0]; //update tail = tmp[1]; nextHead = tmp[2]; } tail.next = nextHead; return newHead; } //返回反转后的:1.头结点 2.尾结点 3.原始尾结点的下一个节点 private ListNode[] reverse(ListNode head, int k){ ListNode nextHead = head; for(int i=0; i<k; i++) nextHead = nextHead.next; // ListNode left=null, cur=head, right; while(k>0){ //save next right = cur.next; //change cur.next = left; //update left = cur; cur = right; k--; } //1. 2. 3. return new ListNode[]{ left, head, nextHead}; }}
力扣优秀题解 递归写法
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode cur = head; int count = 0; while (cur != null && count != k) { cur = cur.next; count++; } if (count == k) { cur = reverseKGroup(cur, k); while (count != 0) { count--; ListNode tmp = head.next; head.next = cur; cur = head; head = tmp; } head = cur; } return head; }
叁歲伎倆
╰+攻爆jí腚メ
还没有评论，来说两句吧...