反转链表 I
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
解题思路
这是一个很简单的题，我们可以定义一个先前结点pre和当前结点cur，将当前结点cur的后继结点设置为先前结点pre，对链表进行遍历一遍就好了。解题代码如下所示：
ListNode* reverseList(ListNode* head) {
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur!=nullptr){
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
反转链表 II
题目描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
解题思路
和反转链表 I 的解题思路接近，因为这次是指定索引的范围进行翻转，所以需要设定一个索引的值index进行计数，其次需要得到index=left的前一个结点和当前结点，并保存下来，便于后续几个片段进行拼接(由于left可能等于1，所以需要设置一个结点指向head，便于得到结果链表)。
参考代码：
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* t=new ListNode(0,head);
if(left==right){
return head;
}
ListNode* pre=t;
ListNode* cur=head;
ListNode* n_left=nullptr;
ListNode* n_right=nullptr;
ListNode* te=nullptr;
bool start=false;
int index=1;
while(cur!=nullptr){
// 结束
if(start && index==right){
n_right=cur->next;
cur->next=pre;
pre=cur;
break;
}
// 开始
if(index==left){
start=true;
n_left=pre;
te=cur;
pre=cur;
cur=cur->next;
index++;
continue;
}
// 反转
if(start){
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
index++;
continue;
}
index++;
pre=cur;
cur=cur->next;
}
// 拼接
if(n_left||n_right){
n_left->next=pre;
te->next=n_right;
}
return t->next;
}
