快手链表题目

上次面试碰到了这个题懵逼了，对链表一点都不熟悉，这次自己磕磕碰碰做了个163ms的解法，还是记录一下
主要的想法：先对于链表翻转，然后对于头节点插入到倒数第k个位置(k一开始为2)，更新头节点，插入倒数到k+2个位置,递归条件终止为k>=len,操作完后再反转回来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
ListNode* reverselist(ListNode *head)
{
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur)
    {
        ListNode* nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    return pre;
}
ListNode* inserttoK(ListNode *head, int k, int len)
{
    if (k >= len) return head;
    ListNode* dummy = new ListNode(-1); dummy->next = head->next;
    auto p = head;
    int count = len - k;
    while (count--)
    {
        p = p->next;
    }
    ListNode* pre = p;
    head->next = pre->next;
    pre->next = head;
    ListNode* newhead = dummy->next;
    return inserttoK(newhead, k + 2, len);
}
    void reorderList(ListNode *head) {
        //先反转  第一插到倒数第二  第二插到倒数第四  第三插到倒数第六
    auto h = reverselist(head);
    auto p = h; int len = 0;
    while (p)
    {
        p = p->next; len++;
    }
    auto newh=inserttoK(h, 2, len);
    auto finalh = reverselist(newh);
    head=finalh;
        return;
    }
};