首页 > 代码库 > [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 m, n 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 反转链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。