题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

每次取出K个节点,翻转该子链表后接入res链表中。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head){  //翻转链表
        if(head==NULL||head->next==NULL) return head;
        ListNode* newhead=reverse(head->next);
        head->next->next=head;
        head->next=NULL;
        return newhead;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL||k==1) return head;
        ListNode *pre=head,*p=head;
        ListNode *newhead=new ListNode(0),*q=newhead;
        int cnt=0;
        while(p){
            if(cnt==k){ //取出K个节点
                pre->next=NULL;
                q->next=reverse(head); //翻转子链表后接入 结果链表中
                while(q->next) q=q->next;
                head=p;
                cnt=0;
            }else{
                pre=p;
                p=p->next;
                cnt++;
            }
        }
        if(cnt!=k) q->next=head;  //最后一组在循环中没有处理
        else q->next=reverse(head);
        return newhead->next;
    }
};
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务