Accepted java solution by reversing the second half


  • 1
    R

    The basic idea is to find the second half, reverse the second half, and merge

    public class Solution {
            public void reorderList(ListNode head) {
                ListNode curr = head;
                int size = 0;
                while (curr!= null) {
                    size++;
                    curr = curr.next;
                }
                if (size <= 2) {
                    return;
                }
                curr = head;
                int count = 1;
                while (count < (size + 1)/2) {
                    curr = curr.next;
                    count++;
                }
                ListNode second = curr.next;
                curr.next = null;
                second = reverse(second);
                curr = head;
                merge(curr, second);
            }
            
            private ListNode reverse(ListNode node) {
                if (node == null)  return node;
                ListNode first = node;
                ListNode second = first.next;
                first.next = null;
                while (second != null) {
                    ListNode tail = second.next;
                    second.next = first;
                    first = second;
                    second = tail;
                }
                return first;
            }
            
            private void merge(ListNode first, ListNode second) {
                while (first != null && second != null) {
                    ListNode secondNext = second.next;
                    second.next = first.next;
                    first.next = second;
                    first = second.next;
                    second = secondNext;
                }
            }
        }

  • 0
    F

    Hi, I am new to this. I am little confusion, would this solution be considered as a in-place solution though?


Log in to reply
 

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