标签搜索

目 录CONTENT

文章目录

分段翻转链表.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 2,228 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

分段翻转链表

@[toc]

一、题目描述

按段(段内的元素不翻转)翻转链表:如链表 1->2->3->4->5->6->7->8->9,如果段大小为3,翻转后为7->8->9->4->5->6->1->2->3。注意段大小作为参数传入。要求编写可以运行的测试用例。

二、分析

  •  第一步把链表整体翻转
  •  第二部按段翻转

三、代码

#include <iostream>
#include <vector>
using namespace std;

struct Node 
{
    Node(int data)
        :_data(data)
         ,next(nullptr)
    {}

    int _data;
    Node* next;
};

//翻转整个链表 OK 
Node* ReverseChild(Node*& root)
{
    if(root->next == nullptr)
    {
        return root;
    }

    Node* last = ReverseChild(root->next);
    root->next->next = root;
    root->next = nullptr;
                                                                                                                                            
    return last;
}

//翻转start和end区间内的链表 OK 
void ReverseOfKChild(Node* start,Node* end)
{
    if(start == nullptr)
    {
        return ;
    }

    //保存上一个节点
    Node* pre = nullptr;

    //保存下一个节点
    Node* Next = nullptr;
    while(start != nullptr)
    {
        //if的作用防止空指针的问题
        if(Next != end)
            Next = start->next;

        //把下一个节点和上一个节点连接起来
        start->next = pre;

        //更新上一个结点的位置
        pre = start;

        //代表start指针已经走到末尾,可以直接结束循环
        if(Next == nullptr || start == end)
        {
            break;
        }                                                                                                                                   

        //把start放到提前保存的Next处
        start = Next;
    }
	return ;
}

//翻转K个一翻转
Node* ReverseOfK(Node* root,int k)
{
    if(k == 0)
    {
        return root;
    }

    //保存记录每个K段的末尾处
    Node* fast = root;

    //这个变量的作用是非常非常非常非常重要的,他是把每个K段的连表连接起来
    Node* pre = nullptr;

    //翻转后的头节点
    Node* head = nullptr;

    //循环遍历
    while(fast != nullptr)
    {
        int t = k;
        //记录每个K段的开始位置
        Node* slow = fast;                                                                                                                  

        //找到每个K段的末尾位置
        while(t > 1)
        {
			if(fast->next == nullptr)
            {
                break;
            }

            fast = fast->next;

            t--;
        }

        //保存头结点
        if(head == nullptr) 
        {
            head = fast;
        }

        //记录每个K段末尾节点的下一个节点,因为一旦前面的发生翻转,
        //那么如果不保存就找不到了
        Node* temp = fast->next;

        //翻转slow和fast区间的节点,该该函数一定不要引用传参,因为在内部会改变slow
        ReverseOfKChild(slow,fast);

        //把每个K段的开始位置(经过翻转后是每个K段的结束位置)和
        //提前保存的temp相连,把相邻的K段节点构成一个链 
        slow->next = temp;

        if(pre != nullptr)
        {
            pre->next = fast;
        }                                                                                                                                   

        //记录上一个slow的位置
        pre = slow;

        //把fast放到提前保存的节点处
 		fast = temp;
    }
    return head;
}

Node* Reverse(Node*& root,int k)
{
    if(root == nullptr)
    {
        return nullptr;
    }

    //9->8->7....->1
    Node* last = ReverseChild(root);

	//7->8->9....->1->2->3
    Node* head = ReverseOfK(last,k);

    return head;
}

//以下都是测试函数
void Print(Node* root)
{
    Node* cur = root;
    while(cur)                                                                                                                              
    {
        printf("%d->\n",cur->_data);
        cur = cur->next;
    }
}

int main()
{
    vector<int> arr {1,2,3,4,5,6,7,8,9,10,11};

    Node* root = nullptr;
    Node* tail = nullptr;
    for(size_t i = 0;i < arr.size();i++)
    {
        if(root == nullptr)
        {
            root = new Node(arr[i]);
            tail = root;
            continue;
        }

        Node* temp = new Node(arr[i]);
        tail->next = temp;
        tail = tail->next;
    }

    int k = 3;

    Print(root);
    cout<<endl;
    Node* head = Reverse(root,k);
    Print(head);                                                                                                                            

    return 0;
}
0

评论区