3ms Java Solution


  • 0
    A
    public class Solution {
        public void reorderList(ListNode head) {
            if(head == null)
            {
                return;
            }
            ListNode fast = head;
            ListNode slow = head;
            while(fast.next != null && fast.next.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
            }
            
            ListNode l1 = reverse(slow.next);
            head = mergeList(head, l1);
        }
        
        private ListNode reverse(ListNode head)
        {
            if (head == null || head.next == null) {
    			return head;
    		}
    		ListNode p1 = head;
    		ListNode p2 = p1.next;
    		head.next = null;
    		while (p1 != null && p2 != null) {
    			ListNode temp = p2.next;
    			p2.next = p1;
    			p1 = p2;
    			p2 = temp;
    		}
    		return p1;
        }
        
        public ListNode mergeList(ListNode a, ListNode b)
        {
            ListNode temp = a;// it will be needed to get the head of the new list
    		while (a != null && b != null) {
    			ListNode a1 = a.next;
    			ListNode b1 = b.next;
    			a.next = b;
    			b.next = a1;
    			a = a1;
    			b = b1;
    		}
    		a.next = null;
            return temp;
        }
    }
    

Log in to reply
 

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