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;

????????????}

????????}

????}

}

?