# 反转链表——leetcode:92/206题
## 简单篇
1. 示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
c++版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode*new_head=NULL;
while(head)//(当链表不为空,即还有节点没有反转)
{
ListNode*next;// 做存储
next=head->next;//(保存链表在该反向节点的后一个节点)
head->next=new_head;//(链表反向,旧头结点反)
new_head=head;//(新头节点后移到刚刚反转的旧节点)
head=next;//(旧头结点移动到下一个需要反转的节点)
}
return new_head;
}
};
![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/20190720131309131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTY5NjQz,size_16,color_FFFFFF,t_70)
这个比较简单,因为是直接把整个链表反转,如果是把当中的某一段反转呢?
## 升级篇
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int list_len=n-m+1;
ListNode *result=head;
ListNode*pre_head=NULL;
while(--m){
pre_head=head;
head=head->next;
}
ListNode*N_L_last=head;
ListNode*new_head=NULL;
while(head&&list_len)
{
ListNode*next=head->next;
head->next=new_head;
new_head=head;
head=next;
list_len--;
}
N_L_last->next=head;
if(pre_head)
pre_head->next=new_head;
else
result=new_head;
return result;
}
};
### 分析:从m到n,m可能为1(从头开始),n也可能为链表长度(到最后)。
一,只需要注意四个关键节点(m-1, m , n , n+1 )其中m-1与n+1可能为不存在的节点。
二,分为两部份处理问题(两边衔接处)
1),如果m=0,则 :result=new_head(直接为反转链表的首元节点)(pre_head此时 为空,没有与new _head建立关系)
如果m!=0, 则 :pre_head=new_head;(将m-1的节点与反转后节点连接)
2)如果n!=表长,反转后的最后一个节点(N_L_last)与n+1节点连接,而此时正好head指向该节点。
如果n=表长,反转后的最后一个节点(N_L_last)的next应该为空,而此时head也为空,就不需要额外处理了。
代码不全,如须查看完整代码,请登入力扣,查看完整版(题号已给出)
作者水平很菜,且是第一次写,希望看完了别伤身体。