力扣 143. 重排链表

题目描述：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解析：

1.判断链表的个数，如果小于等于2，直接返回即可
2.利用快慢指针找到中间节点，将链表分为前后链表
3.定义一个函数，逆转中间节点后面的链表
4.将逆转后的链表插入到前面的链表

Java:

public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        newHead = reverseList(newHead);
        while(newHead != null) {
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }
    private ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode curr = head;
        head = head.next;
        curr.next = null;
        while(head != null) {
            ListNode temp = head.next;
            head.next = curr;
            curr = head;
            head = temp;
        }
        return curr;
    }

JavaScript:

var reorderList = function(head) {
    if(head === null || head.next === null || head.next.next === null) {
        return;
    }
    let slow = head;
    let fast = head;
    while(fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let newHead = slow.next;
    slow.next = null;
    newHead = reverseList(newHead);
    while(newHead !== null) {
        const temp = newHead.next;
        newHead.next = head.next;
        head.next = newHead;
        head = newHead.next;
        newHead = temp;
    }
    function reverseList(head) {
        if(head === null) {
            return null;
        }
        let curr = head;
        head = head.next;
        curr.next = null;
        while(head !== null) {
            const temp = head.next;
            head.next = curr;
            curr = head;
            head = temp;
        }
        return curr;
    }
};