首页 > 代码库 > [LeetCode] Reverse Linked List II
[LeetCode] Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL
, m = 2 and n = 4,
return 1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
方法一:我先写了个简单的reverseList,然后基于reverseList,要找到pre_m, post_n, 然后断开连接,重新连接即可。
吐槽一下LeetCode,竟然是基于打印检测结果,我的程序中有些打印语句,死活过不了,看来半天,没找出问题,去掉打印语句后,就没问题了。。
上code,唯一注意的一点是link是从1 开始的,所以 pre_m 是第m-1个,跳出while循环时,p指向的是第n个,post_n就是p->next.
另外,为了方便出来m=1的情况,加了个dummy的空Node,省去了一大堆判断,是个好方法。。
1 ListNode * reverseList(ListNode* head) 2 { 3 if(head == NULL) return NULL; 4 5 ListNode *pre = NULL; 6 ListNode *cur = head; 7 ListNode *next = NULL; 8 9 while(cur)10 {11 next = cur->next;12 cur->next = pre;13 14 pre = cur;15 cur = next;16 }17 18 return pre;19 20 }21 class Solution {22 public:23 ListNode *reverseBetween(ListNode *head, int m, int n)24 {25 ListNode dummy(100);26 dummy.next = head;27 28 ListNode *pre_m = &dummy;29 ListNode *post_n = NULL;30 ListNode *p = head;31 int cnt = 1;32 33 while(cnt < n)34 {35 if(cnt == (m-1))36 pre_m = p;37 if(p)38 p = p->next;39 cnt++;40 }41 42 post_n = p->next;43 44 // build a signle link, and call reverseList45 p->next = NULL;46 47 //store m node in variable p;48 p = pre_m->next;49 50 pre_m->next = reverseList(pre_m->next); // connect pre_m and n51 52 p->next = post_n; //connect m and post_n53 return dummy.next;54 55 }56 57 };
方法二:不用reverseList,直接原地reverse,注意处理好pre_m 的找法。。
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) 4 { 5 ListNode dummy(-1); 6 dummy.next = head; 7 8 ListNode *pre_m = &dummy; 9 ListNode *p = head;10 int cnt = 1;11 12 for(; cnt < m; cnt ++)13 {14 if(cnt == (m-1))15 pre_m = p;16 p = p->next;17 }18 //now p point to m 19 20 ListNode *pre = NULL;21 ListNode *cur = p;22 ListNode *next = NULL;23 for( cnt = m ; cnt <= n; cnt ++)24 {25 26 next = cur->next;27 cur->next = pre;28 29 pre = cur;30 cur = next;31 }32 // now pre points to n;33 // now cur points to post_n;34 35 pre_m ->next = pre;36 p->next = cur;37 38 return dummy.next;39 }40 41 };
方法三: 方法二中寻找pre_m的方法略微麻烦,有更好的方法,dummy节点的index是0,所以,可以利用这一点去寻找pre_m,下面的代码中p完全可以不要,不过为了清楚,
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) 4 { 5 ListNode dummy(-1); 6 dummy.next = head; 7 8 ListNode *pre_m = &dummy; 9 ListNode *p = head;10 int cnt = 0;11 12 for(; cnt < m-1; cnt ++)13 {14 pre_m = pre_m->next;15 }16 //now pre_m point to m-1;17 p = pre_m->next;18 //now p point to m 19 20 21 ListNode *pre = NULL;22 ListNode *cur = p;23 ListNode *next = NULL;24 for( cnt = m ; cnt <= n; cnt ++)25 {26 27 next = cur->next;28 cur->next = pre;29 30 pre = cur;31 cur = next;32 }33 // now pre points to n;34 // now cur points to post_n;35 36 pre_m ->next = pre;37 p->next = cur;38 39 return dummy.next;40 }41 42 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。