My java solution with O(n) time, O(1) space


  • 0
    L
    public class Solution {
    public void reorderList(ListNode head) {
        if(head==null) return ;
        if(head.next==null) return;
        if(head.next.next==null) return;
        ListNode node1=head.next;
        ListNode node2=head;
        int n=0;
        while(node2!=null) {
            node2=node2.next;
            n++;
        }
        n--;int m=(n+1)/2;
        node2=head;
        while(m-->0) {
            node2=node2.next;
        }
        
        ListNode temp=node2.next,temp2=node2.next,temp3=null;;
        node1=node2.next;node2.next=null;
        node2=node1;node1=head.next;
        while(temp.next!=null)
            temp=temp.next;
        while(temp!=node2) {
            temp2=node2;
            node2=node2.next;
            temp3=temp.next;
            temp.next=temp2;
            temp2.next=temp3;
        }
        temp=head;
        while(node1!=null && node2!=null) {
            temp.next=node2;
            node2=node2.next;
            temp=temp.next;
            temp.next=node1;
            node1=node1.next;
            temp=temp.next;
        }
        if(node1!=null) 
            temp.next=node1;
    }
    

    }


Log in to reply
 

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