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.
题目地址： https://oj.leetcode.com/problems/reverse-linked-list-ii/ 【leetcode:Reverse Linked List II】这道题还是比较简单的，要把链表中从m位置到n位置的节点反序。
我的解法是用一个vector保存从m到n的所有的值，然后第二遍遍历时，从链表m位置对应vector中的最后一个值，n位置对应vector中的第一个值...
代码：
/**
* 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) {
if(head==NULL||head->next==NULL||m==n) return head;
ListNode *p=head;
ListNode *mnode=NULL;
ListNode *nnode=NULL;
vector vi;
int loc=1;
while(loc!=m&&p){
loc++;
p=p->next;
}
mnode=p;
while(loc!=n&&p){
loc++;
vi.push_back(p->val);
p=p->next;
}
vi.push_back(p->val);
nnode=p;
p=mnode;
int i=vi.size()-1;
while(p!=nnode->next){
p->val=vi[i];
i--;
p=p->next;
}return head;
}
};
推荐阅读
- leetcode做题笔记|leetcode:Subsets
- leetcode做题笔记|leetcode:
- leetcode:Decode Ways
- leetcode做题笔记|leetcode:Restore IP Addresses