Reverse a linked list from position m to n. For example: Given 1-2-3-4-5-NULL, m = 2 and n = 4, return 1-4-3-2-5-NULL. 1 ≤ m ≤ n ≤ length of list.
In-place and One-pass
If we want to reverse a linked list, we can put the next node in the front one by one. For example,
A-B-C then B-A-C (put B in the front) then C-B-A (put C in the front).
So the implementation is straightforward, locate the m-th node from the start and put the nodes in the front n-m times.
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 27 28 29 30 | /** * 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) { auto tail = head; ListNode* prev = NULL; for (int i = 0; i < m - 1; i ++) { prev = tail; tail = tail->next; } auto front = tail; for (int i = 0; i < n - m; i ++) { auto tmp = tail->next; tail->next = tail->next->next; tmp->next = front; front = tmp; if (prev) { prev->next = front; } } return prev ? head : front; } }; |
/**
* 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) {
auto tail = head;
ListNode* prev = NULL;
for (int i = 0; i < m - 1; i ++) {
prev = tail;
tail = tail->next;
}
auto front = tail;
for (int i = 0; i < n - m; i ++) {
auto tmp = tail->next;
tail->next = tail->next->next;
tmp->next = front;
front = tmp;
if (prev) {
prev->next = front;
}
}
return prev ? head : front;
}
};–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
239 wordsloading...
Last Post: How to Remove Nth Node From End of List in C/C++?
Next Post: C++ Coding Exercise - Binary Tree Preorder Traversal
