Java Solution, reverse and merge the two half list.


  • 0
    public class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null) return;
        ListNode slow=head,fast=head;
        //find the middle node
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //reverse from the mid node.next 
        ListNode tail=reverseList(slow.next);
        slow.next=null;
        //merge the two half list
        ListNode p=head, q=tail,cur=null,qtmp=null;
        while(p!=null&&q!=null){
            cur=p.next;
            p.next=q;
            qtmp=q.next;
            q.next=cur;
            p=cur;
            q=qtmp;
        }
        
    }
    
     public ListNode reverseList(ListNode head) {
          if(head==null||head.next==null) return head;
            ListNode p=head,q=head.next,tmp;
            p.next=null;
             while(q!=null){
               tmp=q.next;
               q.next=p;
               p=q;
               q=tmp;
            }
            return p;
    

    }
    }


Log in to reply
 

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