[Leetcode] Reverse Linked List II
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.
no words!!!!
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 ListNode *pre, *last; 13 ListNode *h = new ListNode(-1); 14 h->next = head; 15 pre = h; last = head; 16 for (int i = 1; i < m; ++i) { 17 pre = pre->next; 18 } 19 for (int i = 1; i < n; ++i) { 20 last = last->next; 21 } 22 if (pre->next == last) return h->next; 23 ListNode *pos = pre->next, *tmp; 24 pre->next = last; 25 pre = last->next; 26 while (pos != NULL && pos != last) { 27 tmp = pos->next; 28 pos->next = pre; 29 pre = pos; 30 pos = tmp; 31 } 32 pos->next = pre; 33 return h->next; 34 } 35 };