一、Leetcode206题
1.题目
已知链表头结点指针head,将链表逆序。(不可申请额外空间)2.分析
首先看题，不可申请额外空间，但是能创建指针，这很关键
一般链表逆序的思路都是新建一个新指针指向null，这个指针可以从新串的末尾开始逐步扫描到前面
3.代码
#include <stdio.h>
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 = head->next;
head->next = new_head;
new_head = head;
head = next;
}
return new_head;
}
};
int main(){
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = NULL;
ListNode *head = &a;
printf("Before Reversed:n");
while(head){
printf("%dn",head->val);
head = head->next;
}
Solution solve;
head = solve.reverseList(&a);
printf("After reversed:n");
while(head){
printf("%dn",head->val);
head = head->next;
}
return 0;
}
'二、Leetcode92题
1.题目
已知链表头结点指针head,将链表从位置m到n逆序。不可申请额外空间。2.分析
本题相比上面需要考虑的东西会更多一些
1.默认1<=m<n
2.m=1时，需要考虑特殊情况
如果m=1，返回结果的头结点是原来待逆序子串的头
不然，返回结果的头结点就是原来的头结点
3.此外还要考虑子串逆序后的重连操作
3.代码
#include <stdio.h>
struct ListNode{
int val;
ListNode *next;
ListNode(x):val(x),next(NULL){}
};
class Solution{
public:
ListNode* reverseBetween(ListNode *head,int m,int n){
ListNode *result = head;
ListNode *pre_head = NULL;
while(head&&--m){
pre_head = head;
head = head->next;
}
ListNode *modify_list_tail = head;
ListNode *new_head = NULL;
ListNode *next = head;
int change_len = m-n+1;
while(head&&change_len){
next = head->next;
head->next = new_head;
new_head = head;
head = next;
change_len--;
}
modify_list_tail->next = head;
if(pre_head){
pre_head->next = new_head;
}
else
result = new_head;
return result;
}
};
int main(){
ListNode a(10);
ListNode b(20);
ListNode c(30);
ListNode d(40);
ListNode e(50);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = NULL;
ListNode *head = reverseBetween(&a,2,4);
while(head){
printf("%dn",head->val);
head = head->next;
}
}
