题解 | #重排链表#

const int N = 1e4;

typedef struct ListNode* NodePtr;


void reorderList(NodePtr head ) {
  // corrner case
  if (!head || !head->next) return;

  NodePtr stk[N];
  int top = -1;

  NodePtr slow = head, fast = head;
  while (fast && fast->next) {
    *(stk + ++top) = slow;
    slow = slow->next;
    fast = fast->next->next;
  }

  NodePtr p, q = fast ? slow->next : slow, nxt;
  while (top >= 0) {
    p = *(stk + top--);
    nxt = q->next;
    q->next = p->next;
    p->next = q;
    q = nxt;
  }

  slow->next = NULL;
}