reorder-list

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//思路:通过不同的首结点获取到不同的尾结点,然后拼接
public class Solution {
   public ListNode getLastNode(ListNode head)
    {
        ListNode first = head;
        ListNode fakeLast = head;
        if (head.next == null)
        {
            return head;
        }
        while (first.next != null)
        {
            fakeLast = first;
            first = first.next;
        }
        ListNode last = fakeLast.next;
        fakeLast.next = null;
        return last;
    }
 
    public void reorderList(ListNode head)
    {
       if(head==null){
            return;
        }
        // 真的首结点
        ListNode first = head;
        // 假的首结点
        ListNode fakeFirst = head;
        while (first.next != null)
        {
            ListNode last = getLastNode(first);
            fakeFirst = first.next;
            if (fakeFirst == null)
            {
                first.next = last;
                break;
            }
            else
            {
                first.next = last;
                last.next = fakeFirst;
                first = fakeFirst;
            }
 
        }
    }
}