ReverseLinkedListII
Reverse a linked list from positionmton. Do it in-place and in one-pass.For example:Given1->2->3->4->5->NULL,m= 2 andn= 4,return1->4->3->2->5->NULL.Note:Givenm,nsatisfy the following condition:1 ≤m≤n≤ length of list. |
---|
代码
/** * 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
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; }
优质内容筛选与推荐>>