题解 AT1058 【とても長い文字列】

rui_er · 2019-07-09 12:55:08 · 题解

本题的数学方法有过了，我来一发循环链表（C/C++专属福利）。

根据题目意思，要我们循环遍历一个字符串。自然可以想到循环链表。

把样例1建入循环链表长什么样呢？如下图

可以看到效果很好。

关于循环链表的知识

代码：

#include <iostream>
using namespace std;

struct node
{
    char data;
    node* next;
};

int main()
{
    string s;
    int n;
    cin>>s>>n;
    int l = s.length();
    int k;
    node *first, *last;
    first = NULL, last = NULL;
    for(k=0;k<l;k++)
    {
        node *p = new node;
        p->data = s[k];
        p->next = NULL;
        if(k == 0) first = p;
        else
        {
            if(k == l - 1) p->next = first;
            last->next = p;
        }
        last = p;
    }
    last = first;
    for(k=1;k<n;k++,last=last->next);
    cout<<last->data<<endl;
    return 0;
}