java simple solution ,time complex is o(n)


  • 0
    S
    • use the fast and slow pointer,find the middle of list
    • reverse the second half of the list
    • merge The first half of the list and the reverse half of the list
    public class ReorderList {
        public void reorderList(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
    
    
            while (fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
    
            slow = reverseOrderList(slow); //反转后半段链表
            ListNode res = new ListNode(0);
            ListNode curr = res;
            while (head != null && slow != null){  //合并
                curr.next = head;
                head = head.next;
                curr = curr.next;
                curr.next = slow;
                curr = curr.next;
                slow = slow.next;
            }
            if (slow!= null && slow.next != null)
                slow.next = null;
    
            if (head!= null && head.next != null)
                head.next = null;
            LinkedListUtil.outputList(res.next);
        }
    
    
        public ListNode reverseOrderList(ListNode head){
            ListNode pre = null;
            while (head != null){
                ListNode temp = head.next;
                head.next = pre;
                pre = head;
                head = temp;
            }
            return pre;
        }
    
        @Test
        public void test(){
            int[] a = {1,2,3,4,5,6,7,8,9,10};
            ListNode head = LinkedListUtil.arrayToList(a);
           // LinkedListUtil.outputList(reverseOrderList(head));
            reorderList(head);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.