将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
数据范围: , ,链表中每个元素都满足
要求空间复杂度 ,时间复杂度
要求空间复杂度 ,时间复杂度
例如:
给定的链表是
对于 , 你应该返回
对于 , 你应该返回
{1,2,3,4,5},2
{2,1,4,3,5}
{},1
{}
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ #include <stdlib.h> struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here //考虑k为0或1以及链表为空、链表长度为1的情况 if(k < 2 || head == NULL || head->next == NULL) { return head; } //思路:每k个节点为一组,每个组逐个翻转(循环嵌套) //1.遍历得出链表长度 int count = 1;//用于记录链表长度 struct ListNode* pa = head; while (pa->next != NULL) { count++; pa = pa->next; } //2.分组翻转 //插一个新的首节点,用于锁定翻转后新链表的真正首节点 struct ListNode *newhead = malloc(sizeof(struct ListNode)); newhead->next = head;//新节点插在首节点之前,作为暂时的假的首节点 struct ListNode *pLeft = newhead; struct ListNode *pMid = newhead; struct ListNode *pRight = NULL; //遍历翻转 for (int i = 0; i < (count / k); i++) {//外循环,i为组号,每k个一组,分组遍历翻转 pLeft = pMid; pMid = pMid->next; for (int j = 1; j < k; j++) {//内循环,j为每组中节点序号,每组各自进行翻转 pRight = pMid->next; pMid->next = pRight->next; pRight->next = pLeft->next; pLeft->next = pRight; } } return newhead->next;//返回真正的首节点 }
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here if (head == NULL || head->next == NULL) { return head; } struct ListNode *newnode = malloc(sizeof(struct ListNode)); newnode->next = head; struct ListNode *cur = newnode, *prev = newnode; struct ListNode *next = NULL; //计算链表长度 int cnt = 1; struct ListNode *len = head; while (len->next != NULL) { cnt++; len=len->next; } for (int i = 0; i < (cnt/k); i++) { prev = cur; cur = cur->next; for (int j = 1; j < k; j++) { next = cur->next; cur->next = next->next; next->next = prev->next; prev->next = next; } } return newnode->next; }
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ #include <stdlib.h> /* struct ListNode* reverseKGroup(struct ListNode* head, int k ) { struct ListNode *res=(struct ListNode*)malloc(sizeof(struct ListNode)); res->next=head; if(head==NULL) { return NULL; } struct ListNode *pre=res; //获得链表长度 int n=1; struct ListNode *length=head; while (length->next!=NULL) { n++; length=length->next; } for(int i=0;i<(n/k);i++) { struct ListNode *cur=pre->next; for(int j=1;j<k;j++) { struct ListNode *head1=cur->next; cur->next=head1->next; head1->next=pre->next; pre->next=head1; } pre=cur; } return res->next; } */ //sosososososososososo goodgood struct ListNode* reverseKGroup(struct ListNode* head, int k ) { struct ListNode *tail=head;//找到每次翻转的尾部!!!!!*** //遍历k次到尾部 for(int i=0;i<k;i++) { if(tail==NULL) { return head; } tail=tail->next; } struct ListNode *pre=NULL; struct ListNode *cur=head; while (cur!=tail) { struct ListNode *head1=cur->next; cur->next=pre; pre=cur; cur=head1; } head->next=reverseKGroup(tail, k); return pre; }
struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here struct ListNode *tail = head; //1、递归结束的点(k个为一组,不足k个直接返回head) for (int i = 0; i < k; i++){ if (tail == NULL) { return head; } tail = tail->next; } struct ListNode *pre = NULL; struct ListNode *cur = head; struct ListNode *nex; //2、每一级的任务 while (cur != tail) { nex = cur->next; cur->next = pre; pre = cur; cur = nex; } head->next = reverseKGroup(tail, k); //3、找到返回值 return pre; }
#include <stdlib.h> struct ListNode* reverseKGroup(struct ListNode* head, int k ) { struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode)); phead->next = head; struct ListNode *prior = head, *rear = head, *cur = head, *temp = cur; for(int i = 0; i < k - 1 && rear; i++){ rear = rear->next; } if(!rear || k == 1){ return head; } else { struct ListNode *cur_following = head->next; //phead指向第一轮最后一个元素 phead->next = rear; while(rear){ rear = rear->next;//rear位于第k+1个位置 for (int i = 0; i < k - 1; i++) { //反转 temp = cur_following; cur_following =cur_following->next; temp->next = cur; cur = temp; if(rear){ rear = rear->next; } } if(rear){ //还有下一轮反转,则上一轮第一个节点指针域改为下一轮最后一个元素, // 否则改为下一轮第一个元素,也就是一轮循环后cur_following的位置 prior->next = rear; prior = cur_following; //如果说还有下一轮还需要反转,则cur需要跟第一轮一样移动到下一轮第一个位置上, // 保持跟第一轮反转之前的状态一样,否则下面一轮第一个元素也被反转了,指针域连到上一轮最后一个。 cur = cur_following; cur_following = cur_following->next; } else { prior->next = cur_following; } } return phead->next; } }
struct ListNode* reverseKGroup(struct ListNode* head, int k ){ if(k == 1)//每一个一组等于不逆置 return head; if(!head)//是否为空表 return head; struct ListNode* low = head; struct ListNode* high = head; struct ListNode* plow = NULL; struct ListNode* lhigh = NULL; struct ListNode* p = NULL; struct ListNode* q = NULL; struct ListNode* tlow = NULL; int i = 0, n = 0;//i用来判断未逆置链表中是否有连续k个节点,n判断是否是第一次逆置 for(i = 1; i <= k && high; i++){ if(i == k){ i = 1; n++; tlow = low; lhigh = high->next; p = low->next; q = p->next; low->next = NULL;//摘头节点逆置法 while(p != lhigh){ p->next = tlow; tlow = p; p = q; if(q) q = p->next; }//逆置 if(n == 1){ plow = head; head = high; }//判断是否是第一次逆置 else plow->next = high; low->next = lhigh; plow = low; high = p; low = p; } if(high) high=high->next;//写for里会导致溢出 } return head; }
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include <stdio.h> /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here if(head == NULL || head->next == NULL || k == 1) { return head; } int iNodeNums = 0; struct ListNode* pHead = NULL, *pTail = NULL, *ptr1 = head; while (ptr1) { iNodeNums++; ptr1 = ptr1->next; } iNodeNums /= k; if (iNodeNums == 0) { return head; } ptr1 = head; while(iNodeNums--){ struct ListNode* ptr2 = ptr1, *ptr3 = NULL, *ptr4 = NULL; int i = k; while (i-- && ptr2) { printf("i:%d, head : %d\n", i, ptr2->val); ptr3 = ptr2->next; ptr2->next = ptr4; ptr4 = ptr2; ptr2 = ptr3; } if (pHead) { pTail->next = ptr4; }else { pHead = ptr4; } pTail = ptr1; ptr1 = ptr3; } if (ptr1) { pTail->next = ptr1; } return pHead; }
struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here if (head == NULL) return NULL; if (head->next == NULL || k == 1) return head; typedef struct ListNode Node; Node top; top.val = 0; top.next = head; Node *res = ⊤ Node *pre = res; Node *cur = res->next; int sum = 0, flag = 0, index = 1; while (head != NULL) { sum++; head = head->next; } flag = sum / k; while (cur->next != NULL) { if (!flag) break; if (index < k) { Node *temp = cur->next; cur->next = temp->next; temp->next = pre->next; pre->next = temp; index++; }else { pre = cur; cur = cur->next; index = 1; flag--; } } return res->next; }