leetcode Reverse Nodes in k-Group翻转链表K个一组

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

/**

 * 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* reverseKGroup(ListNode* head, int k) {

        ListNode* node = head;

        //第一个k个

        for(int i=0;i<k;i++){

            if(!node)

                return head;//不到k个长

            node = node->next;

        }

        //node是last的后一个

        ListNode* new_head = reverse(head,node);

        //关键递归

        head->next = reverseKGroup(node,k);

        return new_head;

    }

    //翻转链表 1 2 3

    ListNode* reverse(ListNode* head,ListNode* last){

        //last是翻转链表的后一个节点

        ListNode *pre=last, *cur=head;

        while(cur != last){

            ListNode* Next = cur->next;

            cur->next = pre;

            pre = cur;

            cur = Next;

        }

        return pre;

    }

};

巴特西

leetcode Reverse Nodes in k-Group翻转链表K个一组

最新文章

热门文章