Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
AC code:
/**
* 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) {
ListNode* dummy = new ListNode(0);
ListNode* pre = new ListNode(0);
ListNode* cur = new ListNode(0);
dummy->next = head;
pre = dummy;
cur = dummy->next;
for (int i = 1; i < m; ++i) {
pre = pre->next;
cur = cur->next;
}
for (int i = 0; i < n-m; ++i) {
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
return dummy->next;
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Reverse Linked List II.
core code：
for (int i = 0; i < n-m; ++i) {
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
step 1:
1 2 3 4 5
pre
cur
temp
cur->next = temp->next; 2 -> 4
temp->next = pre->next; 3 -> 2
pre->next = temp; 1 -> 3
step 2:
1 2 3 4 5
pre
cur
temp
cur->next = temp->next; 2 -> 5
temp->next = pre->next; 4 -> 3
pre->next = temp; 1 -> 4
原文：https://www.cnblogs.com/ruruozhenhao/p/9867143.html