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. |
|---|
代码
代码语言：js复制/**
* 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) {
// Start typing your C/C solution below
// DO NOT write int main() function
if (head == NULL) return NULL;
if (m == n) return head;
ListNode *last = new ListNode(0);
last->next = head;
ListNode *p1 = head;
head = last;
for (int i = 1; i < m; i)
{
p1 = p1->next;
last = last->next;
}
ListNode *first = p1;
ListNode *p2 = p1->next;
ListNode *p3;
for (int i = m; i < n; i)
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
last->next = p1;
first->next = p2;
return head->next;
}
};看到有大神给出了神级的代码：
http://discuss.leetcode.com/questions/267/reverse-linked-list-ii
代码语言：js复制Way 1:
ListNode *reverseBetween(ListNode *head, int m, int n) {
if (!head) return head;
ListNode dummy(0);
dummy.next = head;
ListNode *preM, *prev = &dummy;
for (int i = 1; i <= n; i ) {
if (i <= m) {
if (i == m) preM = prev;
prev = head;
head = head->next;
} else { //m < i <=n
prev->next = head->next;
head->next = preM->next;
preM->next = head;
head = prev->next;
}
}
return dummy.next;
}
Way 2:
ListNode *reverseBetween(ListNode *head, int m, int n) {
if (!head) return head;
ListNode dummy(0);
dummy.next = head;
ListNode *prev = &dummy;
ListNode *curr = head;
int i = 0;
while (curr && i<n) {
if (i<m) prev = curr;
curr = curr->next;
}
curr = reverse(prev, curr->next);
return dummy.next;
}
ListNode *reverse(ListNode *begin, ListNode *end)
{
ListNode *last = begin->next;
ListNode *curr = last->next;
while (curr != end) {
last->next = curr->next;
curr->next = begin->next;
begin->next = curr;
curr = last->next;
}
return last;
}
