首页 > 其他 > 详细

[LeetCode] Reverse Linked List II

时间:2014-06-28 13:21:10      阅读:308      评论:0      收藏:0      [点我收藏+]

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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn 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 reverseList
45             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 n
51 
52             p->next = post_n; //connect m and post_n
53             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 };

 

 

[LeetCode] Reverse Linked List II,布布扣,bubuko.com

[LeetCode] Reverse Linked List II

原文:http://www.cnblogs.com/diegodu/p/3798714.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!