jeudi 4 août 2022

Problems with LinkedList, overwritten?

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