Solution with explaination


  • 0
    D
            if (head == null || head.next == null) return;            
            //step 1 divide into two list
            ListNode slow = head, fast = head;//use slow and fast to search for the mid point
            while (fast.next != null)
            {
                fast = fast.next;
                if (fast.next != null) fast = fast.next;
                else break;
                slow = slow.next;
            }
            //deal with two list here: slow is the mid point now
            ListNode list1 = head;
            ListNode list2 = slow.next;
            slow.next = null;
            //step2 reverse seconde list
            if (list2 == null || list2.next == null){
            }
            else if (list2.next.next == null)
            {
                ListNode rev = list2.next;
                rev.next = list2;
                list2.next = null;
                list2 = rev;
            }
            else
            {
                ListNode p1 = list2;
                ListNode p2 = list2.next;
                ListNode p3 = list2.next.next;
                p1.next = null;
                while (p3 != null)
                {
                    p2.next = p1;
                    p1 = p2;
                    p2 = p3;
                    p3 = p3.next;
                }
                p2.next = p1;
                list2 = p2;
            }
            //step3 merge list1 and list2
            while (list2 != null)
            {
                ListNode tmp1 = list1.next;
                ListNode tmp2 = list2.next;
                list1.next = list2;
                list2.next = tmp1;
                list1 = tmp1;
                list2 = tmp2;
            }

Log in to reply
 

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