image.png

解題思路: 找出Middle node, 返反middle node後面的node
再續個插入構成新的鏈表

我的code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //解題思路:reverse後半部份, 將前半段連接reverse後的後半段
        //快慢指針取得middle node
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
    
        //此時slow應在1234的2如長度為雙數, 在12345中的3如長度為單數
        //如鏈表為雙數, fast.next應不為空 e.g. 1234, after 1 loop, slow=2, fast=3, fast.next=4!=null
        //如鏈表為雙數, 則取反轉snow.next, 反之也是反轉snow.next, 因為12345, 上半部份為123, 下半部份為45 
        //決定鏈表長度是否基數
        boolean odd = fast.next==null?false:true;
        
        //反轉下半部份
        ListNode second = reverseList(slow.next);
        
        ListNode first = head;
        
        //連接兩部份構成新的node
        while(second!=null){
            ListNode fnext = first.next; //儲存原本的first.next;
            ListNode snext = second.next;//儲存原本的second.next;
            first.next = second; 
            //如果odd==true, second.next = null
            second.next = odd==true?fnext:null;
            //順移first & second
            first = fnext;
            second =snext;
        }
        //此時second為fnext, first指向second 最後的node
        //如odd == ture, second 指向fnext 即12345的3, 此時將first指向null並返回first即可
        
    }
    public ListNode reverseList(ListNode head){
        ListNode p1 = head;
        ListNode p2 = head.next;
        p1.next = null;
        while (p2!=null){
            //儲存p2.next 作為之後的p3
           ListNode p3 = p2.next;
            //將p2指向p1;
            p2.next = p1;
            //順移p1,p2
            p1 = p2;
            p2 = p3;
            
        }
        return p1;
        
    }
}

別人的代碼: (重點是切斷middle與middle.next的連接with middle.next =null)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public static void reorderList(ListNode head) {
        if(head!=null&&head.next!=null)
        {
        ListNode middle=getMideeldofList(head);
        ListNode next=middle.next;
        middle.next=null;  //重點是切斷middle與middle.next的連接with middle.next =null
        ListNode backNode=ReverseList(next);
        ListNode cur=head,cur1=backNode;
        ListNode next1=null,next2=null;
        while(cur!=null&&cur1!=null)
        {
             next1=cur.next;
             next2=cur1.next;
             cur.next=cur1;
             cur1.next=next1;
             cur=next1;
             cur1=next2;
        }
        }
        
        
        
        
    }
    public static ListNode getMideeldofList(ListNode head)
    {
        if(head==null||head.next==null)
            return head;
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            
        }
        return slow;
    }
    public static ListNode ReverseList(ListNode head)
    {
        if(head==null||head.next==null)
            return head;
        ListNode fakeNode=new ListNode(-1);
        fakeNode.next=head;
        ListNode pre=fakeNode,cur=head.next,firstNode=head;
        while(cur!=null)
        {
            ListNode next=cur.next;
            cur.next=pre.next;
            pre.next=cur;
            cur=next;
        }
        firstNode.next=null;
        return fakeNode.next;
    }
// --------------------- 
// 版权声明：本文为CSDN博主「yvanbu」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。
// 原文链接：https://blog.csdn.net/u012249528/article/details/45566441
}