Last active
December 12, 2015 10:19
-
-
Save zhoutuo/4757816 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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 | |
int ttt = m; | |
ListNode tmpHead(-1); | |
tmpHead.next = head; | |
ListNode* mHead = &tmpHead; | |
while(--m) { | |
mHead = mHead->next; | |
} | |
ListNode* nNode = &tmpHead; | |
++n; | |
while(n--) { | |
nNode = nNode->next; | |
} | |
ListNode* mNode = mHead->next; | |
ListNode bHead(-1); | |
bHead.next = nNode; | |
while(mNode != nNode) { | |
ListNode* tmp = mNode->next; | |
mNode->next = bHead.next; | |
bHead.next = mNode; | |
mNode = tmp; | |
} | |
mHead->next = bHead.next; | |
if(ttt == 1) { | |
return bHead.next; | |
} else { | |
return head; | |
} | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for singly-linked list. | |
* public class ListNode { | |
* int val; | |
* ListNode next; | |
* ListNode(int x) { | |
* val = x; | |
* next = null; | |
* } | |
* } | |
*/ | |
public class Solution { | |
public ListNode reverseBetween(ListNode head, int m, int n) { | |
// create a pre head pointing to head | |
ListNode preHead = new ListNode(-1); | |
preHead.next = head; | |
ListNode runner = preHead; | |
// go to the pointer just before mth node | |
for(int i = 1; i < m; ++i) { | |
runner = runner.next; | |
} | |
// save the nodes after nth in backup.next | |
ListNode tail = preHead; | |
// this needs go beyond the nth element, that's why i starts with 0 | |
for(int i = 0; i < n; ++i) { | |
tail = tail.next; | |
} | |
ListNode backup = new ListNode(-1); | |
backup.next = tail.next; | |
tail.next = null; | |
// reverse the part | |
runner.next = reverseList(runner.next); | |
// append the tail (backup) | |
ListNode current = preHead.next; | |
while(current.next != null) { | |
current = current.next; | |
} | |
current.next = backup.next; | |
return preHead.next; | |
} | |
private ListNode reverseList(ListNode head) { | |
// -1 -> null | |
ListNode preHead = new ListNode(-1); | |
// current(1) -> 2 -> 3 -> 4 -> 5 -> null | |
ListNode current = head; | |
while(current != null) { | |
ListNode tmp = current.next; | |
current.next = preHead.next; | |
preHead.next = current; | |
current = tmp; | |
} | |
return preHead.next; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment