Leetcode--Reverse Linked List
2018-06-27 10:06:04来源:未知 阅读 ()
转自请注明: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; } } };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:WA自动鸡
下一篇:贪心算法推导 水题~
- STL之list 2020-04-30
- stl_list复习 2020-02-10
- stl源码学习(版本2.91)--list 2019-11-05
- C++ 线性表实现 2019-05-22
- [转]C++ STL list的初始化、添加、遍历、插入、删除、查找、 2019-02-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash