recorder-list

题目：Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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}.

解析：该题来自leetcode，做法不太推荐。思想是把节点的都获取到，然后按照题目想要的顺序去记录下，然后创建单链表返回即可。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.ArrayList;
import java.util.List;
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null){
              return;
        }
        List<Integer> result = new ArrayList<>();//记录变换后的值
        List<Integer> list = new ArrayList<>();//记录原始遍历的值
        ListNode p = head;
        while (p!=null){
            list.add(p.val);
            p=p.next;
        }
        if(list.size()==1){
            return;
        }
        int start =0;
        int end =list.size()-1;
        while (start<=end){//获取题目想要的值的样子
            if(start==end){
                result.add(list.get(start));
                break;
            }
            result.add(list.get(start));
            result.add(list.get(end));
            start++;
            end--;
        }
        ListNode head2 = new ListNode(result.get(0));
        for(int i=result.size()-1;i>=1;i--){//头插法创建单链表
            ListNode node = new ListNode(result.get(i));
            node.next=head2.next;
            head2.next=node;
        }
        if(head!=null){//leetcode的提交和其他的不一样，如果不是这样赋值，直接传递引用head=head2;就不行了，head不会指向head2指向的对象，也是醉了。应该和他的系统的判定方式有关
            head.val= result.get(0);
            head.next=head2.next;
        }
    }
}