Leetcode--Reverse Linked List
转自请注明：http://www.cnblogs.com/igoslly/p/8670038.html
链表逆序在链表题目中还是较为常见的，这里将Leetcode中的两道题放在一起，分别是
0092 Reverse Linked List II 和 0206 Reverse Linked List，0092在0206的基础上，提出了部分逆序的概念
首先来看0206，题目描述为：Reverse a singly linked list.
也就是给出一个链表，要求我们将链表全部倒置链接
想法1： 定义一个堆栈，遍历链表时均push入堆栈，pop的顺序即为逆序
/**
* 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) {
stack<ListNode*> list_stack; // 元素堆栈
ListNode *p = head;
// 当链表为空时，直接返回空
if(head==NULL){return NULL;}
// 循环结束后，p为链表最后一个有值的结点（非NULL）
while(p->next!=NULL){
list_stack.push(p);
p=p->next;
}
// 逆序表表头为原链表末结点，即为p
head=p;
while(!list_stack.empty()){
ListNode *q = list_stack.top();
list_stack.pop();
p->next=q;
p=p->next;
}
// 此时p是原链表首元素，新链表末元素，必须赋值NULL，否则提交回超时
p->next=NULL;
return head;
}
};
按照此方法提交后，Leetcode runtime 是 9ms
程序的时间复杂度是 O(2n)，因为遍历两次；
空间复杂度是 O(n)，stack大小取决于原链表的大小。
想法2： 在遍历原链表时，直接创造新逆序链表，想法大概如下：
/**
* 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!=NULL){
ListNode * next=head->next;
head->next=new_head;
new_head=head;
head=next;
}
return new_head;
}
};
这种方法程序的时间复杂度，因为只遍历了一遍，是 O(n)，同时也没有耗费多余的空间
再看题目0092，题目描述是
|
Reverse a linked list from position m to n. Do it in-place and in one-pass. For example:
return
Note: |
要求原链表里[m,n]位置的结点进行逆序 同时保证输入m，n合法
注意: 这里结点计算从1开始 |
相对与题1来说，题2中相对于逆序段的逆序过程不变，只是多出了逆序段前后结点连接的问题，涉及到的结点有：
①逆序段开始的前一个结点 before_modify ②逆序段开始的第一个结点 first_modify
③逆序段结束的最后一个结点 last_modify ④逆序段结束后的后一个结点 after_modify
正常的链表顺序是 ① -> ② -> ③ -> ④
逆序后链表顺序是 ① -> ③ -> ② -> ④
/**
* 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) {
ListNode * pre_head =NULL,*p=head;
// pre_head=before_reverse, p=first_reverse
ListNode * new_head=NULL;
int cnt=0; //count linked list position
// 使用p和pre_head确定逆序段开始结点和前结点的位置
while(p!=NULL){
cnt++;
if(cnt==m){break;}
pre_head=p;p=p->next;
}
// 循环结束后，pre_head即为前结点位置（1），p为逆序段开始位置（2）
// 因为后面循环p位置会改变，所以此时做下记录
// 在逆序后，此结点（2）就作为逆序段末结点，直接连接后续的结点
ListNode * reverse_first=p;
// 逆序段开始逆序
while(cnt<=n){
ListNode *Next=p->next;
p->next=new_head;
new_head=p;
p=Next;
cnt++;
}
// 循环结束后，此时p为逆序段结束的后一个结点（4），连接在reverse_first（2）后面
reverse_first->next=p;
// 注意:当m=1时，pre_head=NULL，直接返回逆序链表的new_head即可
// 否则，将new_head连接在前面正常后，返回原链表的head
if(pre_head!=NULL){
pre_head->next=new_head;return head;
}else{
return new_head;
}
}
};