?前段时间帮对象做360笔试题时，遇到一个没怎么想明白的编程题，直到今天刷力扣遇到了相似的k个一组翻转链表后，想着在做一下那天的编程题，就想着记录一下遇到的难点。
?力扣题如下图所示：
360原创题如下：
代码如下：
class Solution {
public:
? ? pair<ListNode*,ListNode*> myReverse(ListNode* head,ListNode* pre1){
? ? ? ? ListNode* prev = pre1->next;
? ? ? ? ListNode* p = head;
? ? ? ? while(pre1!=prev){
? ? ? ? ? ? ListNode* temp = p->next;
? ? ? ? ? ? p->next=prev;
? ? ? ? ? ? prev = p;
? ? ? ? ? ? p = temp;
? ? ? ? ? ? }
? ? ? ? ? ? return {pre1,head};
? ? ? ? } ? ?//head,pre1是原链表的位置，注意注意!
? ? ListNode* reverseKGroup(ListNode* head, int k) {
? ? ? ? if(head->next->next==NULL) return head;
? ? ? ? ListNode* hair = new ListNode(0);
? ? ? ? hair->next = head; ? ? ? ? ? ?// //返回的头结点
? ? ? ? ListNode* pre1 =head; ? ? ? ? //翻转的尾节点 ? ? ?
? ? ? ? ListNode* cur = head->next; ?//翻转尾节点的下一个节点
? ? ? ? ListNode* pre2 = head; ? ? ? ?//固定每个头结点的上个节点
? ? ? ? while(head->next){
? ? ? ? ? ? while(cur->next!=NULL && (pre1->val==cur->val || cur->val==cur->next->val){
? ? ? ? ? ? ? ? cur = cur->next;
? ? ? ? ? ? ? ? pre1 = pre1->next;
? ? ? ? ? ? }
? ? ? ? ? ? head = cur;
? ? ? ? ? ? pre2 = pre1;
? ? ? ? ? ? while(cur->next!=NULL && pre1->val!=cur->val && cur->val!=cur->next->val){
? ? ? ? ? ? ? ? pre1 = cur;
? ? ? ? ? ? ? ? cur = cur->next;
? ? ? ? ? ? }
? ? ? ? ? ? if(cur->next ==NULL && pre2 != pre1){ ? ?//最后节点翻转的情况
? ? ? ? ? ? ? ? pre1 = cur;
? ? ? ? ? ? ? ? cur =NULL;
? ? ? ? ? ? ? ? pair<ListNode*,ListNode*> result = myReverse(head,pre1);
? ? ? ? ? ? ? ? head = result.first;
? ? ? ? ? ? ? ? pre1 = result.second;
? ? ? ? ? ? ? ? pre2->next = pre1;
? ? ? ? ? ? ? ? head->next = cur;
? ? ? ? ? ? }
? ? ? ? ? ? else if(pre2 == pre1){ ? ? ? //最后节点不翻转的情况
? ? ? ? ? ? ? ? return hair->next;
? ? ? ? ? ? }
? ? ? ? ? ? else if(cur->next!=NULL){ ? ? ? //中间节点翻转的情况
? ? ? ? ? ? ? ? pair<ListNode*,ListNode*> result = myReverse(head,pre1);
? ? ? ? ? ? ? ? head = result.first;
? ? ? ? ? ? ? ? pre1 = result.second;
? ? ? ? ? ? ? ? pre2->next = pre1;
? ? ? ? ? ? ? ? head->next = cur;
? ? ? ? ? ? ? ? pre1 = cur;
? ? ? ? ? ? ? ? cur = cur->next;
? ? ? ? ? ? ? ? }?}? }
? ? ? ? return hair->next;
? ? }
};
链表题虽然想法不难实现，但一些细节、边界问题还是很容易出现错误，这里特别是处理右边界的时候，弄的我很迷糊，一开始代码还是比较简洁的，加了很多测试案例后发现原代码行不通，再次基础上又添添补补，导致代码比较冗长，也算是一次心酸的添补史吧！剪枝的操作日后在想吧，哪位大佬有更简洁直观的代码可以分享我一下，感激不尽~