Lintcode 450.K组翻转链表

题目描述：给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。

链表元素个数不是k的倍数，最后剩余的不用翻转。

这种链表的题，一般就是采用模拟法，在coding的时候可以写一些链表操作的注释帮助自己写代码的过程中知道自己进行到哪一步了，此外这道题用到了dummy节点。

小知识：

什么时候使用dummy节点呢？

当链表结构发生变化时，你return的头节点不再是它给你的时候，就可能需要使用dummy节点。

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: a ListNode
     * @param k: An integer
     * @return: a ListNode
     */
    ListNode * reverseKGroup(ListNode * head, int k) {
        //D->1->2->3->[4->5->6]->7  此处可以看出要翻转456,受影响的点除了456本身还有3,因此借用dummy节点解决问题
        //D->[3->2->1]->[6->5->4]->7
        ListNode* dummy;
        dummy->next = head;
        
        ListNode* prev = dummy;//前继节点指向dummy
        while (nullptr != prev) {
            prev = reverseKnode(prev, k);
        }
        return dummy->next;
    }
    
    //对head后面k个节点进行翻转，若不够k则返回nullptr，不翻转
    //head->n1->n2->n3...nk-1->nk->nk+1
    //=>
    //head->nk->nk-1...n3->n2->n1->nk+1
    ListNode* reverseKnode(ListNode *head, int k) {
        //1. 找到第k个节点
        ListNode* curt = head;
        ListNode* n1 = head->next;
        for (int i = 0; i < k; ++i) {
            curt = curt->next;
            if (nullptr == curt) {
                return nullptr;
            }
        }
        ListNode* nk = curt;
        ListNode* nkplus = curt->next;
        
        //2. 进行翻转
        ListNode* prev = head;
        curt = head->next;
        while (curt != nkplus) {
            ListNode* tmp = curt->next;
            curt->next = prev;
            prev = curt;
            curt = tmp;
        }
        
        //head<->n1->n2->...nk->nk+1   =>   head->nk->nk-1...->n2->n1->nk+1
        head->next = nk;
        n1->next = nkplus;
        
        return n1;
    }
    
};