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