143. Reorder List（好）

L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,

Given ​​{1,2,3,4}​​, reorder it to ​​{1,4,2,3}​​.

​​Subscribe​​ to see which companies asked this question

这是一道比较综合的链表操作的题目，要按照题目要求给链表重新连接成要求的结果。其实理清思路也比较简单，分三步完成：

（1）将链表切成两半，也就是找到中点，然后截成两条链表；

（2）将后面一条链表进行reverse操作，就是反转过来；

（3）将两条链表按顺序依次merge起来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  void reorderList(ListNode* head) {
    if (head == NULL || head->next == NULL) return;
    ListNode* faster = head;
    ListNode* slower = head;
    while (faster->next&&faster->next->next){
      faster = faster->next->next;
      slower = slower->next;
    }
    ListNode* head2 = slower->next;
    slower->next = NULL;

    ListNode* pre = NULL;
    while (head2){
      ListNode* next = head2->next;
      head2->next = pre;
      pre = head2;
      head2 = next;
    }
    
    ListNode* p1 = head->next, *p2 = pre;
    ListNode* p = head;

    int cnt = 1;
    while (p1&&p2){
      if (cnt & 1){
        p->next = p2;
        p2 = p2->next;
      }
      else{
        p->next = p1;
        p1 = p1->next;
      }
      cnt++;
      p = p->next;
    }

    if (p1){
      p->next = p1;
    }
    if (p2){
      p->next = p2;
    }

  }

};