网络异常，图片无法展示
|
给定一个单链表 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, 5 * 104] 1 <= node.val <= 1000
本题要我们将链表重新排列，排列的规则是 1->n->2->n-1->...
要完成这样的操作，首先需要拿到后面的节点，而且要从后向前依次拿
根据这样的需求，可以首先将输入链表转为双向链表
然后定义两个指针 pre,next，初始指向头节点和尾节点
然后让 pre.next = next,达到第一个节点指向最后一个节点的目的
接着让 next.next = pre.next，达到最后一个节点指向第二个节点的目的
然后更新 pre = pre.next,next = next.pre,重复以上过程
直到两个指针相遇，这里需要将链表中的环解开
相遇的条件是 pre.next = next 或者 pre = next,此时的环其实都在 next 指针指
向的节点上， 通过将 next.next = null，将环解开即可
整体过程如下：
网络异常，图片无法展示
|
代码如下：
var reorderList = function(head) { let pre = head,next = pre.next; // 将原链表转为双向链表 while(next){ next.pre = pre; pre = next; next = pre?pre.next:null; } // pre指向头节点，next指向尾节点 next = pre,pre = head; // 通过将pre.next = next,next.next = pre.next实现链表的重新排列 while(pre.next!==next && pre!==next){ const pre_next = pre.next; pre.next = next; next.next = pre_next; pre = pre_next; next = next.pre; } // 解除链表中的环 next.next = null; }; 复制代码
至此我们就完成了 leetcode-143-重排链表
如有任何问题或建议，欢迎留言讨论！
