每日OJ_牛客_反转部分单向链表

目录

牛客_反转部分单向链表

解析代码

---

牛客_反转部分单向链表

反转部分单向链表__牛客网

题目给的代码‘：

#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 L,int R) {// 在下面完成代码
}
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;
}

---

解析代码

可以用双指针解决，但假设需要反转的链表部分，占比比较大，则需要两次遍历链表来实现。

1. 遍历确定反转链表的起始位置
2. 遍历链表进行反转

那是不是可以考虑一次遍历链表就解决该问题？ 可以采用头插的方式一次遍历解决问题、

题解及函数代码：

Node* reversePart(Node* head, int L, int R) {// 在下面完成代码Node* pHead = new Node;pHead->next = head;Node* prevNode = pHead;for (int i = 0; i < L - 1; i++) // 找到左结点的前一个{prevNode = prevNode->next;}Node* cur = prevNode->next;for (int i = 0; i < R - L; ++i) // R - L 次头插{Node* nextNode = cur->next;cur->next = nextNode->next;nextNode->next = prevNode->next;prevNode->next = nextNode;}Node* list = pHead->next;free(pHead);return list;
}