Reverse Linked List II [LeetCode]

时间:2023-12-25 12:24:25

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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Summary: First writes down the reverse parts (m to n) , then handles nodes before the m-th node and after the n-th node.

 class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode * current = head;
ListNode * pre_m_node = NULL;
ListNode * new_head = NULL;
int i = ;
while(current != NULL) {
if(i == m -)
break;
pre_m_node = current;
i ++;
current = current -> next;
}
//reverse m to n
ListNode * pre_n_node = current;
int num_of_reverse_op = ;
int num_of_nodes_to_reverse = n - m + ;
while(num_of_reverse_op < num_of_nodes_to_reverse) {
ListNode * pre_head = new_head;
new_head = current;
current = current -> next;
num_of_reverse_op ++;
new_head -> next = pre_head;
}
//connect rest node after the nth node
pre_n_node -> next = current; if(pre_m_node != NULL) {
pre_m_node -> next = new_head;
return head;
} else {
return new_head;
}
}
};