力扣算法题-25.K个一组翻转链表 C语言实现

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例： 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5

说明： 你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

思路

1、遍历链表，记录k个节点的起始节点，累计满k个节点，根据起始节点进行翻转即可； 2、最后记得连接剩余不满足k个节点的节点即可； 调试过程中遇到几次时间超限，但是看着代码又没有死循环，感觉自己眼神不好了，后来发现是链表没有连接好，链表有环了。

程序

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseKGroup(struct ListNode* head, int k){ int i = 0; struct ListNode* node = head; struct ListNode* pre = NULL; struct ListNode* sonnode = NULL; struct ListNode* sonhead = NULL; struct ListNode* sonpre = NULL; struct ListNode* sonnext = NULL; /*k值为1，直接返回原链表即可*/ if(k==1) return head; while(node){ i++; /*记录k个节点的起点*/ if(i==1){ sonhead = node; } node = node->next; /*满足k个链表后，将k个链表进行翻转*/ if(i==k){ /*翻转k链表*/ sonpre = NULL; sonnode = sonhead; while(i>0 && (sonnode != NULL)){ i--; sonnext = sonnode->next; sonnode->next = sonpre; sonpre = sonnode; sonnode = sonnext; } if(pre == NULL){ head=sonpre; }else{ pre->next = sonpre; } i=0; pre = sonhead; sonhead = NULL; } } /*链接后续不满k的链表*/ if(sonhead != NULL && pre != NULL){ pre->next = sonhead; } return head; }