Problem: Reverse a linked list from position m to n. Do it in-place and in one-pass.
Solution:
/**
* 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;
}
ListNode *iter = head;
int i;
for (i = 1; i < m-1; i++)
iter = iter->next;
// Now iter points to (m-1)th node if m > 1.
ListNode* cur, *curNext, *prev, *startReversing;
// cur node at which we start reversing the link list.
// prev node refer to node before cur.
// Storing the first node, where linklist started reversing
if (m == 1) {
cur = iter;
prev = NULL;
} else {
cur = iter->next;
prev = iter;
}
startReversing = cur;
// Reversing the linklist.
for (i = n-m; i > 0; i--) {
curNext = cur->next;
cur->next = prev;
prev = cur;
cur = curNext;
}
if ( m != n) {
// Now curNext point to (n+1)th node.
curNext = cur->next;
cur->next = prev;
// Set the next of mth node (starting node of linklist reversal) to (n+1)th node.
startReversing->next = curNext;
}
if (m == 1) {
// Return nth node.
return cur;
} else {
// Set the next of (m-1)th node to reverse linklist head.
iter->next = cur;
}
return head;
}
};
============ Another Solution ==================
/**
* 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
ListNode *first = head, *store_first = NULL, *next = head, *prev = NULL, *prev_join = NULL;
int count = n - m;
while (m > 1) {
prev_join = first;
first = first->next;
m--;
}
while ( count >= 0) {
next = first->next;
first->next = prev;
if (prev == NULL) {
store_first = first;
}
prev = first;
first = next;
count--;
}
store_first->next = first;
if (prev_join != NULL) {
prev_join->next = prev;
} else {
return prev;
}
return head;
}
};
No comments:
Post a Comment