题解 | #重排链表#

方法一

1. 求出链表的长len，将链表从中间分成两个链表list1和list2。其中list1为前半段，长度为(len + 1) / 2
2. 将list2逆置。可以采用头插法，即遍历list2，将每个节点从头部插入到初始为空的链表newList中。
3. 将list1与newList合并。这步就很简单了

方法二

1. 遍历链表，将每个节点地址插入数组arr
2. i,j分别指向数组首尾，逐渐向中间靠拢，直到i > j，
3. 靠拢过程中，每次取arr[i]和arr[j]分别插入到初始为空的链表newList。（注意，i==j时，插入一个即可）

说明

方法二实现简单，有点取巧，额外占用空间稍多。代码按方法一实现。

class Solution {
public:
    int getListLen(ListNode *head) {
        int len = 0;
        while (head)
        {
            len++;
            head = head->next;
        }
        return len;
    }

    ListNode *reverseList(ListNode *head) {        
        ListNode *newHead = NULL;
        ListNode *p = head;

        while (p)
        {
            ListNode *q = p->next;
            p->next = newHead;
            newHead = p;
            p = q;
        }

        return newHead;
    }
    
    void reorderList(ListNode *head) {
        int len = getListLen(head);
        len = (len + 1) / 2;
        ListNode *p = head;
        for (int i = 0; i < len - 1; i++)
        {
            p = p->next;
        }

        if (!p)
        {
            return;
        }

        ListNode *head2 = p->next;
        
        p->next = NULL;
        head2 = reverseList(head2);

        p = head;
        ListNode *q = head2;
        while (p && q)
        {
            ListNode *r = p->next;
            ListNode *s = q->next;
            p->next = q;
            q->next = r;
            p = r;
            q = s;            
        }
    }
};