程序员代码面试指南 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;                             //返回反转后的链表头
}

主要是为左程云的《程序员代码面试指南》这本书改写C++版的题解。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
07-21 12:41
已编辑
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务