程序员代码面试指南 2.12：将单链表的每K个节点之间逆序

1、思路

• 用双指针标记链表中每段为K个节点长度的首尾节点，反转当前段，保存当前段反转后的头结点newHead，递归进入下一段的反转；

• 若tail尾结点已经指向空，则返回链表。

2、代码

list_node* reverse(list_node* head, list_node* tail)    //反转链表模板
{
    auto pre = head, cur = head->next;
    while (cur != tail)
    {
        auto ne = cur->next;
        cur->next = pre;
        pre = cur, cur = ne;
    }

    head->next = nullptr;
    return pre;
}

list_node * reverse_knode(list_node * head1, int K)
{
    if (head1 == nullptr || head1->next == nullptr) return head1;

    list_node* tail = head1;
    for (int i = 0; i < K; ++ i)
    {
        if (tail == nullptr) return head1;      //链表若不足K个节点，则直接返回
        //注意，如果这里面试官要求最后不足k个也要翻转，就得改成下面一行
        //if (tail == nullptr) return reverse(head, tail);
        tail = tail->next;
    }

    //反转当前K个节点长度的链表，head1在反转后变成了当前段的尾结点
    list_node* newHead = reverse(head1, tail);  
    head1->next = reverse_knode(tail, K);       //递归地进行下一段链表的反转

    return newHead;                             //返回反转后的链表头
}