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
Solution:
- Store the m – 1 and m-th item as prev and tail before reversing
- Reverse the m to n, return the head and tail->next of the reversed list
- Reconnect prev and head, tail and tail->next
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode dummy(0); dummy.next = head; ListNode* p = &dummy; // Find the m-1 th node for (int i = 0; i < m - 1; ++i) p = p->next; ListNode* prev = p; ListNode* curr = p->next; ListNode* tail = curr; // Reverse from m to n for (int i = m; i <= n; ++i) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } // Connect three parts p->next = prev; tail->next = curr; return dummy.next; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: dummy = ListNode(0) dummy.next = head p = dummy for i in range(m - 1): p = p.next prev = p curr = p.next tail = curr for i in range(n - m + 1): next = curr.next curr.next = prev prev = curr curr = next p.next = prev tail.next = curr return dummy.next |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment