Problems with LinkedList, overwritten?-CodePudding

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

CodePudding user response：

The variables that are of the ListNode* type, are pointers. They are not the structures themselves. It may help to visualise this. When the while loop starts, we might have this state:

head  headFirstHalf
  │    │
  ▼    ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘


┌────────────┐   ┌────────────┐
│ data: 4    │   │ data: 3    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘
  ▲
  │
headSecondHalf

Then we execute

ListNode *temp = headFirstHalf->next;

head  headFirstHalf  temp
  │    │              │
  ▼    ▼              ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘


┌────────────┐   ┌────────────┐
│ data: 4    │   │ data: 3    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘
  ▲
  │
headSecondHalf

Now we get to the statements that you asked about. First:

headFirstHalf->next = headSecondHalf;

head  headFirstHalf  temp
  │    │              │
  ▼    ▼              ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ─┐   │   │ next: null │
└────────│───┘   └────────────┘
         │
         ▼
┌────────────┐   ┌────────────┐
│ data: 4    │   │ data: 3    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘
  ▲
  │
headSecondHalf

And then

headFirstHalf = temp;

head  headFirstHalf  temp
  │    └───────────┐  │
  ▼                ▼  ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ─┐   │   │ next: null │
└────────│───┘   └────────────┘
         │
         ▼
┌────────────┐   ┌────────────┐
│ data: 4    │   │ data: 3    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘
  ▲
  │
headSecondHalf

This should already be enough to answer your question, but let's just finish the rest of the body of the while loop.

temp = headSecondHalf->next;

head  headFirstHalf
  │    └───────────┐
  ▼                ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ─┐   │   │ next: null │
└────────│───┘   └────────────┘
         │
         ▼
┌────────────┐   ┌────────────┐
│ data: 4    │   │ data: 3    │
│ next: ───────► │ next: null │
└────────────┘   └────────────┘
  ▲                ▲
  │                │
headSecondHalf    temp

Continue with:

headSecondHalf->next = headFirstHalf;

head  headFirstHalf
  │    └───────────┐
  ▼                ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ─┐   │ ┌►│ next: null │
└────────│───┘ │ └────────────┘
         │     │
         ▼     │
┌────────────┐ │ ┌────────────┐
│ data: 4    │ │ │ data: 3    │
│ next: ───────┘ │ next: null │
└────────────┘   └────────────┘
  ▲                ▲
  │                │
headSecondHalf    temp

And finally:

headSecondHalf = temp;

head  headFirstHalf
  │    └───────────┐
  ▼                ▼
┌────────────┐   ┌────────────┐
│ data: 1    │   │ data: 2    │
│ next: ─┐   │ ┌►│ next: null │
└────────│───┘ │ └────────────┘
         │     │
         ▼     │
┌────────────┐ │ ┌────────────┐
│ data: 4    │ │ │ data: 3    │
│ next: ───────┘ │ next: null │
└────────────┘   └────────────┘
                   ▲ ▲
  ┌────────────────┘ │
headSecondHalf      temp

Then the next iteration starts...

I hope this has clarified it.