首页 > 代码库 > [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:
Given1->2->3->4->5->NULL, m = 2 and n = 4,

return1->4->3->2->5->NULL.

Note: 
 Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

题目中有两点需要注意的是:一、m和n数字和结点的对应关系;二、1 ≤ m ≤ n ≤ length of list,意味着,第一,可以从表头开始反转,第二,不用考虑n>length of list的情况。

思路:因为可以从表头开始反转,所以要new一个nList。首先要找到反转的起始结点cur和其前驱pre,然后将前驱pre的后继为cur的next,而cur的后继则为后继的后继,cur后继的后继为pre的后继。有点拗口!脑海中可以想象为,整个过程,pre不动,cur本身指向的结点不动,但给人的感觉是不断后移的。以1->2->3->4->5->NULL, m = 2 and n = 4,为例。

技术分享        技术分享

另外值得注意的是,代码中,两个for循环的使用。代码如下:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *reverseBetween(ListNode *head, int m, int n) 
12     {
13         if(head==NULL)  return NULL;
14 
15         ListNode *nList=new ListNode(0);
16         nList->next=head;
17 
18         ListNode *cur=head;
19         ListNode *pre=nList;
20         for(int i=1;i<m;++i)
21         {
22             pre=cur;
23             cur=cur->next;
24         }
25         for(int i=0;i<n-m;++i)
26         {
27             ListNode *temp=cur->next;
28             cur->next=temp->next;
29             temp->next=pre->next;
30             pre->next=temp;
31         }
32         return nList->next;
33     }
34 };

//或者也可以,分成三部分,m之前,[m,n],n之后,然后将[m,n]进行反转,然后连接三段。

[Leetcode] Reverse linked list ii 反转链表