1074 Reversing Linked List

题意：

每k个元素反转链表，不足k个就不反转。如原链表为1→2→3→4→5→6，k=3，则反转后的链表为3→2→1→6→5→4；若k=4，则反转后的链表为4→3→2→1→5→6。

思路：

这题会比较烦，写代码前一定要现在纸上理清思路，写出关键代码，不然出了错再改来改去真的很浪费时间，要是考试的话估计心态就蹦了。本题是比较经典的“反转链表（指反转整条链表）”的升级版，但做法是一样的。我们可以把“反转”这一动作单独抽象成一个函数，然后遍历链表，每遍历k个结点（假设是pi...pj），就把pi...pj这个子链表进行反转，易错点在于每k个子链表之间该如何衔接而确保不会断链，具体看代码，我已经注释的很详细了。

注：本题是关于“链表”操作非常经典的题目，应当熟练掌握，因为这是非常非常基础的问题。另外，个人觉得有必要说一下的是，网上很多的解题报告，以及《算法笔记》里的题解，都不是真正的“反转”操作，虽然也能AC，但不利于真正掌握链表、指针的操作，有些投机取巧。要是面试写白板代码的时候写成那种样子，是要被鄙视的。

代码：

#include <cstdio>

;
struct Node{
    int data;
    int curr,next;
}LinkList[N];

//反转操作,记录新链表的头结点和尾结点
//传入时,tail==head，记得加“&”
void reverseLinkList(int& head,int& tail)
{
    //如果链表为空，或者只有一个结点，则直接返回
     || LinkList[head].next==-) return;
    ,p=head;//p为工作指针
    tail=LinkList[head].curr;
    ){
        int next=LinkList[p].next;
        )
            head=p;//如果next为空，则当前结点为最后一个结点，令其为新链表的头结点
        LinkList[p].next=pre;
        pre=p;
        p=next;
    }
}

int main()
{
    //freopen("pat.txt","r",stdin);
    int n,k,head;
    scanf("%d%d%d",&head,&n,&k);
    int curr,data,next;
    ;i<n;i++){
        scanf("%d%d%d",&curr,&data,&next);
        LinkList[curr].data=data;
        LinkList[curr].curr=curr;
        LinkList[curr].next=next;
    }
    int p=head;
    ,tail=-;
    ){
        ;
         && cnt<k){
            p=LinkList[p].next;
            cnt++;
        }
        ){
            int tmp=p;
            p=LinkList[p].next;//先更新，再截断
            LinkList[tmp].next=-;//把子链表截断
            //翻转当前含有k个结点的子链表，并分别记录其头结点和尾结点
            int tmptail=tmphead;
            reverseLinkList(tmphead,tmptail);
            ) newhead=tmphead;
            else LinkList[tail].next=tmphead;
            tail=tmptail;//更新尾结点
        }else{
            LinkList[tail].next=tmphead;//剩余不足k个结点,就把剩余部分直接链在tail后面
            p=-;//别忘了
        }
    }
    p=newhead;
    ){
        printf("%05d %d ",LinkList[p].curr,LinkList[p].data);
        ) printf("%05d\n",LinkList[p].next);
        else printf("-1\n");
        p=LinkList[p].next;
    }
    ;
}

【第一次限时AC的时候是这么做的，但这不是纯正“翻转”操作】

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
;
struct Node{
    int data;
    int curr,next;
}LinkList1[N],LinkList2[N];

int main()
{
    //freopen("pat.txt","r",stdin);
    int n,k,head;
    scanf("%d%d%d",&head,&n,&k);
    int curr,data,next;
    ;i<n;i++){
        scanf("%d%d%d",&curr,&data,&next);
        LinkList1[curr].data=data;
        LinkList1[curr].curr=curr;
        LinkList1[curr].next=next;
    }
    ;
    ,pre=-;
    vector<Node> temp;
    ){
        temp.push_back(LinkList1[p]);
        cnt++;
        if(cnt==k){
            reverse(temp.begin(),temp.end());
            ){
                newhead=temp[].curr;
                pre=newhead;
            }else{
                LinkList2[pre].next=temp[].curr;
                pre=temp[].curr;
            }
            ;
            <temp.size();i++){
                LinkList2[pre].data=temp[i].data;
                LinkList2[pre].curr=temp[i].curr;
                LinkList2[pre].next=temp[i+].curr;
                pre=temp[i+].curr;
            }
            LinkList2[pre].data=temp[i].data;
            LinkList2[pre].curr=temp[i].curr;
            LinkList2[pre].next=-;
            //注意别忘了重置
            cnt=;
            temp.clear();
        }
        p=LinkList1[p].next;
    }
    ){
        LinkList2[pre].next=temp[].curr;
        pre=temp[].curr;
        ;
        <temp.size();i++){
            LinkList2[pre].data=temp[i].data;
            LinkList2[pre].curr=temp[i].curr;
            LinkList2[pre].next=temp[i+].curr;
            pre=temp[i+].curr;
        }
        LinkList2[pre].data=temp[i].data;
        LinkList2[pre].curr=temp[i].curr;
        LinkList2[pre].next=-;
    }
    p=newhead;
    ){
        printf("%05d %d ",LinkList2[p].curr,LinkList2[p].data);
        ) printf("%05d\n",LinkList2[p].next);
        else printf("-1\n");
        p=LinkList2[p].next;
    }
    ;
}

巴特西

1074 Reversing Linked List

最新文章

热门文章