Simple java solution with explanation


  • 0
    T
    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null)
                return;
                
            // get second half of the list
            ListNode p1 = head, p2 = head;
            while (p2 != null && p2.next != null) {
                p1 = p1.next;
                p2 = p2.next.next;
            }
            
            // reverse second half of the list
            ListNode prev = null;
            ListNode curr = p1.next;
            ListNode tmp;
            
            while (curr != null) {
                tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }
            
            ListNode second = prev;
            p1.next = null;
            
            // insert second half to first half
            p1 = head;
            p2 = second;
            ListNode tmp1, tmp2;
            
            while (p2 != null) {
                tmp1 = p1.next;
                p1.next = p2;
                tmp2 = p2.next;
                p2.next = tmp1;
                p1 = tmp1;
                p2 = tmp2;
            }
        }
    }

Log in to reply
 

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