143. Reorder List

二刷

一直在找原来的list截断点在哪里，这个阶段点的next要设为null否则就会形成环
后来发现最后的slow就是这个点
slow.next = null就可以了

99.20 %
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast == null) {
            fast = slow;
        } else {
            fast = slow.next;
        } 
        ListNode prev = null, curr = fast, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        slow = head;
        fast = prev;
        while (fast != null) {
            next = fast.next;
            fast.next = slow.next;
            slow.next = fast;
            slow = slow.next.next;
            fast = next;
        }
        slow.next = null;
    }
}

一刷

这道题做的特别愚蠢，本来mergeTwo就是一个很简单的每个list去一个然后穿起来
然而做的时候无脑背模板自动写成merge sort了
简直是有病

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode mid = findMin(head);
        ListNode midplus = mid.next;
        mid.next = null;
        head = mergeTwo(head, reverseList(midplus));
    }
    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode curr = head;
        ListNode next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = l1;
        l1 = l1.next;
        ListNode curr = head;
        while (l1 != null & l2 != null) {
            //System.out.println("here");
            curr.next = l2;
            l2 = l2.next;
            curr = curr.next;
            curr.next = l1;
            l1 = l1.next;
            curr = curr.next;
        }
        if (l1 == null) curr.next = l2;
        if (l2 == null) curr.next = l1;
        return head;
    }
 
    private ListNode findMin(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}