题目
给定一个单链表 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]
解题
方法一：将链表存储在容器中+双指针
class Solution { public: void reorderList(ListNode* head) { vector<ListNode*> arr; ListNode* cur=head; while(cur){ arr.push_back(cur); cur=cur->next; } cur=head; int l=0,r=arr.size(); while(l<r){ if(l<r){ cur->next=arr[--r]; cur=cur->next; } if(l<r){ cur->next=arr[++l]; cur=cur->next; } } arr[l]->next=nullptr; } };
java
class Solution { public void reorderList(ListNode head) { List<ListNode> ls=new LinkedList<>(); ListNode cur=head; while(cur!=null){ ls.add(cur); cur=cur.next; } int l=0,r=ls.size()-1; while(l<r){ ls.get(r).next=ls.get(l).next; ls.get(l).next=ls.get(r); l++; r--; } ls.get(l).next=null; return; } }
