I have recently been working on this problem: Reorder List - Leetcode 143 and found out I don't have the concept of Linked List as clear as I imagined. The answer looks as following (got it from Grokking the coding interview):
static void reorder(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return;
}
// find the middle of the LinkedList
ListNode *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// slow is now pointing to the middle node
ListNode *headSecondHalf = reverse(slow); // reverse the second half
ListNode *headFirstHalf = head;
// rearrange to produce the LinkedList in the required order
while (headFirstHalf != nullptr && headSecondHalf != nullptr) {
ListNode *temp = headFirstHalf->next;
headFirstHalf->next = headSecondHalf;
headFirstHalf = temp;
temp = headSecondHalf->next;
headSecondHalf->next = headFirstHalf;
headSecondHalf = temp;
}
// set the next of the last node to 'null'
if (headFirstHalf != nullptr) {
headFirstHalf->next = nullptr;
}
}
The problem comes in the following part:
headFirstHalf->next = headSecondHalf;
headFirstHalf = temp;
If I overwrite the next node of headFirstHalf to be the node headSecondHalf and then I overwrite the headFirstHalf, wouldn't I be overwriting the headFirstHalf->next by assigning headFirstHalf to temp?
I hope the question is clear, otherwise I'll try to make myself clearer, Thanks
Aucun commentaire:
Enregistrer un commentaire