36. Reverse Linked List II
Reverse a linked list from position m to n.
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
Have you met this question in a real interview?
Example
Example 1:
Input: 1->2->3->4->5->NULL, m = 2 and n = 4,
Output: 1->4->3->2->5->NULL.
Example 2:
Input: 1->2->3->4->NULL, m = 2 and n = 3,
Output: 1->3->2->4->NULL.
ListNode * reverseBetween(ListNode * head, int m, int n) {
// write your code here
if(head == NULL || head->next == NULL){
return head;
}
if(m == n){
return head;
}
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *copy = dummy;
for(int i = 0; i < m - 1; i++){
dummy = dummy->next;
}
ListNode *preStart = dummy;
ListNode *start = dummy->next;
dummy = dummy->next;
ListNode *pre = NULL;
for(int i = 0; i < n - m + 1; i++){
ListNode *temp = dummy->next;
dummy->next = pre;
pre = dummy;
dummy = temp;
}
start->next = dummy;
preStart->next = pre;
return copy->next;
}
Description
中文
English
Reverse a linked list from position m to n.
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
Have you met this question in a real interview?
Example
Example 1:
Input: 1->2->3->4->5->NULL, m = 2 and n = 4,
Output: 1->4->3->2->5->NULL.
Example 2:
Input: 1->2->3->4->NULL, m = 2 and n = 3,
Output: 1->3->2->4->NULL.
Comments
Post a Comment