题解 | #反转部分单向链表#

#include <iostream>
using namespace std;
struct Node {
    int val;
    struct Node* next;
};
Node* input_List() {
    int n,val;
    Node* phead=new Node();
    Node* pcur=phead;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>val;
        if(i==1) {
            pcur->val=val;
            pcur->next=nullptr;
        }
        else {
            Node* new_pNode=new Node();
            new_pNode->val=val;
            new_pNode->next=nullptr;
            pcur->next=new_pNode;
            pcur=new_pNode;
        }
    }
    return phead;
}
Node* reversePart(Node* head,int from,int to) {
    int len=0;
    Node* node1=head;
    Node* fPos=nullptr;
    Node* tPos=nullptr;
    while(node1!=nullptr) {
        len++;
        fPos=len==from-1?node1:fPos;
        tPos=len==to+1?node1:tPos;
        node1=node1->next;
    }
    if(from>to || from<1 || to>len) {
        return head;
    }
    node1=fPos==nullptr?head:fPos->next;
    Node* node2=node1->next;
    node1->next=tPos;
    Node* next=nullptr;
    while(node2!=tPos) {
        next=node2->next;
        node2->next=node1;
        node1=node2;
        node2=next;    
    }
    if(fPos!=nullptr) {
        fPos->next=node1;
        return head;
    }
    return node1;
}
int main() {
    Node* phead=input_List();
    int L,R;
    cin>>L>>R;
    Node* new_phead=reversePart(phead,L,R);
    while(new_phead!=nullptr) {
        cout<<new_phead->val<<" ";
        new_phead=new_phead->next;
    }
    cout<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")