购物中心网站建设,六安政务中心网站,ucenter wordpress,关键词搜索优化【问题描述】[第25题][K个一组反转链表][困难]
时间复杂度#xff1a;O(N^2) 空间复杂度#xff1a;O(1)
java
给你一个链表#xff0c;每 k 个节点一组进行翻转#xff0c;请你返回翻转后的链表。k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数…【问题描述】[第25题][K个一组反转链表][困难]
时间复杂度O(N^2) 空间复杂度O(1)
java
给你一个链表每 k 个节点一组进行翻转请你返回翻转后的链表。k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。示例给你这个链表1-2-3-4-5当 k 2 时应当返回: 2-1-4-3-5当 k 3 时应当返回: 3-2-1-4-5说明你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。【解答思路】
1. 图解大法
1.链表分区为已翻转部分待翻转部分未翻转部分 2.每次翻转前要确定翻转链表的范围这个必须通过 k 此循环来确定 3.需记录翻转链表前驱和后继方便翻转完成后把已翻转部分和未翻转部分连接起来 4.初始需要两个变量 pre 和 endpre 代表待翻转链表的前驱end 代表待翻转链表的末尾 5.经过k此循环end 到达末尾记录待翻转链表的后继 next end.next 6.翻转链表然后将三部分链表连接起来然后重置 pre 和 end 指针然后进入下一次循环 7.特殊情况当翻转部分长度不足 k 时在定位 end 完成后endnull已经到达末尾说明题目已完成直接返回即可 时间复杂度为 O(n*K) 最好的情况为 O(n) 最差的情况未 O(n^2) 空间复杂度为 O(1) 时间复杂度O(N) 空间复杂度O(1)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head null || head.next null){return head;}//定义一个假的节点。ListNode dummynew ListNode(0);//假节点的next指向head。// dummy-1-2-3-4-5dummy.nexthead;//初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点ListNode predummy;ListNode enddummy;while(end.next!null){//循环k次找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空end.next会报空指针异常。//dummy-1-2-3-4-5 若k为2循环2次end指向2for(int i0;ikend ! null;i){endend.next;}//如果endnull即需要翻转的链表的节点数小于k不执行翻转。if(endnull){break;}//先记录下end.next,方便后面链接链表ListNode nextend.next;//然后断开链表end.nextnull;//记录下要翻转链表的头节点ListNode startpre.next;//翻转链表,pre.next指向翻转后的链表。1-2 变成2-1。 dummy-2-1pre.nextreverse(start);//翻转后头节点变到最后。通过.next把断开的链表重新链接。start.nextnext;//将pre换成下次要翻转的链表的头结点的上一个节点。即startprestart;//翻转结束将end置为下次要翻转的链表的头结点的上一个节点。即startendstart;}return dummy.next;}//链表翻转// 例子 head 1-2-3-4public ListNode reverse(ListNode head) {//单链表为空或只有一个节点直接返回原单链表if (head null || head.next null){return head;}//前一个节点指针ListNode preNode null;//当前节点指针ListNode curNode head;//下一个节点指针ListNode nextNode null;while (curNode ! null){nextNode curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。curNode.nextpreNode;//将当前节点next域指向前一个节点 null-1-2-3-4preNode curNode;//preNode 指针向后移动。preNode指向当前节点。curNode nextNode;//curNode指针向后移动。下一个节点变成当前节点}return preNode;}}2. 递归 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;}// 反转前 k 个元素ListNode newHead reverse(head, tail);//下一轮的开始的地方就是tailhead.next reverseKGroup(tail, k);return newHead;}/*左闭又开区间*/private 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;}
【总结】
1.链表题目多画图 画图大法好
2.整条链表翻转 例子 head 1-2-3-4public ListNode reverse(ListNode head) {//单链表为空或只有一个节点直接返回原单链表if (head null || head.next null){return head;}//前一个节点指针ListNode preNode null;//当前节点指针ListNode curNode head;//下一个节点指针ListNode nextNode null;while (curNode ! null){nextNode curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。curNode.nextpreNode;//将当前节点next域指向前一个节点 null-1-2-3-4preNode curNode;//preNode 指针向后移动。preNode指向当前节点。curNode nextNode;//curNode指针向后移动。下一个节点变成当前节点}return preNode;}3.常规解法
将链表指针全部复制到数组进行调整后再连接的算法
转载链接https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/
转载链接https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/di-gui-java-by-reedfan-2/
