题目内容

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

示例 1:

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示

1、链表的长度范围为 [1, 5 * 10^4]
2、1 <= node.val <= 1000

题解

本题考查双指针算法。

通过题，我们首先能发现，重新拼接的链表是一半一半的规律，前一半不动，后一半翻转的同时接到前一半每两个节点之间。因此我们可以模拟这个过程，然后把最后的链表给搞出来。

分两步处理：

1、首先，让后半段的链表指针反向，整个链表变成：

L1→L2→L3→…→L⌈n/2⌉←L⌈n/2⌉+1←…←Ln。

2、然后，用两个指针分别从1和n的位置开始往中间扫描，将后半段交替插入到前半段即可。

这里要注意一下，因为链表数量可能是奇数可能是偶数，因此奇数时，两个链表中间会有中点，这个点是最后的结尾点，需要让其next为null；如果是偶数点，那么链表可以刚好分半，那么最后一个点就是第二部分链表的第一个节点，要让其的next为null。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;//当头结点为空时，直接返回
        int n = 0;//定义链表的长度变量
        for(auto p = head; p; p=p->next) n++;//求链表长度
        auto mid = head;//找到中点的位置
        for(int i = 0; i < (n + 1)/2 -1; i++) mid = mid->next;

        auto tail = mid;
      	//将后半段反转
        for(auto p = mid, q = mid->next; q;){
            auto next = q -> next;
            q->next = p, p = q, q = next;
            tail = p;
        }
      	//修改链表排序
        for(auto p = head, q = tail; q != mid;){
            auto next = q->next;
            q->next = p->next;
            p->next = q;
            p = p->next->next, q = next;
        }
      	//用奇偶数来判断那个节点为尾结点，尾结点的next为空。
        if(n % 2) mid->next = NULL;
        else mid->next->next = NULL;
    }
};