Split, Reverse and Merge


  • 0
    1. Find middle of list and split the list into two.
    2. Reverse the second list.
    3. Merge the lists by switching between the two lists.
        public void ReorderList(ListNode head) {
            if (head == null) {
                return;
            }
    
            ListNode list2 = Split(head);
            if (list2 == null)
            {
                return;
            }
    
            ListNode reverseHead = Reverse(list2);
    
            ListNode resultHead = head;
            if (head != null)
            {
                ListNode p1 = head;
                head = head.next;
                int swap = 1;
                do
                {
                    if (swap == 0)
                    {
                        p1.next = head;
                        head = head.next;
                        swap = 1;
                    }
                    else
                    {
                        p1.next = reverseHead;
                        reverseHead = reverseHead.next;
                        swap = 0;
                    }
    
                    p1 = p1.next;
                }
                while (head != null && reverseHead != null);
                if (head != null)
                {
                    p1.next = head;
                    p1 = p1.next;
                }
    
                if (reverseHead != null)
                {
                    p1.next = reverseHead;
                    p1 = p1.next;
                }
            }
    
            head = resultHead;
        }
    
        public ListNode Reverse(ListNode head)
        {
            ListNode p1 = head;
            ListNode p2 = p1;
            if (p2 != null)
            {
                p2 = p2.next;
            }
    
            p1.next = null;
    
            while (p2 != null)
            {
                ListNode nextP2 = p2.next;
                p2.next = p1;
                p1 = p2;
                p2 = nextP2;
            }
    
            return p1;
        }
    
        public ListNode Split(ListNode list1)
        {
            ListNode middle = list1;
            ListNode end = list1;
            do
            {
                int r = 2;
                while (r > 0)
                {
                    if (end != null)
                    {
                        end = end.next;
                    }
    
                    r--;
                }
    
                if (end != null && middle != null)
                {
                    middle = middle.next;
                }
            }
            while (end != null);
            ListNode retValue = middle.next;
            middle.next = null;
            return retValue;
        }

Log in to reply
 

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