【leetcode刷题笔记】025.Reverse Nodes

日期：20180915

题目描述：

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.

详解：

首先要知道普通的反转链表该如何实现，需要定义三个指针，分别指向当前节点，前面的节点和后面的节点。这样才能不让链表断裂。

这道题我首先编写了一个函数，用来实现K个节点的链表的反转。函数中，判断是否为空，是否足够K个元素是必要的边界条件判断。更重要的是这个函数除了反转k个元素的链表，它的返回值是什么。是最后一个值还是下一个值，如果是最后一个值，比如上面k=3的例子中，如果返回3，那4就找不到了，3和4之间就断了。如果返回4，那3就找不到了。所以我们在这个实现K个节点反转的函数中，把3连到4上。如果后面没有了就连空指针。这样返回3，再找返回值的下一个节点就找到了4。

然后在主函数中要不断调用这个函数，直到最后是空指针。这里，依然需要三个指针。所以我们可以总结一下，凡是要连接链表，一般都需要三个指针，一个pre指着前一个值，一个cur指着当前值，一个nxt把下一个先存起来。这样在连接的时候才不会断裂。

下面是我的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //先来编写一个函数，只反转k个节点
    ListNode*  rK(ListNode* head,int k){
        //空的直接返回
        if(head==NULL){
            return NULL;
        }
        //如果不够长，直接返回，什么都不做
        ListNode* behind = head;
        for(int i=0;i<k;i++){
            if(behind == NULL){
                return head;
            }
            behind = behind->next;
        }
        //满足长度，反转
        ListNode* pre = NULL;
        ListNode* nxt = NULL;
        ListNode* cur = head;
        for(int i = 0;i<k;i++){
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        head->next = cur;
        return pre;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* a = head;
        ListNode* tmp = head;
        ListNode* b = new ListNode(0);
        ListNode* res = b;
        while(a){
            tmp = rK(a,k);
            b ->next = tmp;
            b = a;
            a = a->next;
            tmp = a;
        }
        return res->next;
        
        
    }
};