力扣 148. 排序链表 & 234. 回文链表

148题目描述：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表。

解析：

1.快慢指针找出中间节点，分成两个链表
2.分别对两个链表进行归并排序
3.最后合并两个链表

Java:

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    private ListNode mergeSort(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next, left, right;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        right =mergeSort(slow.next);
        slow.next = null;
        left = mergeSort(head);
        return mergeList(left, right);
    }
    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode curr = new ListNode(0);
        ListNode dummy = curr;
        while(left != null && right != null) {
            if(left.val < right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        if(left != null) {
            curr.next = left;
        }
        if(right != null) {
            curr.next = right;
        }
        return dummy.next;
    }
}

JavaScript:

var sortList = function(head) {
    return mergeSort(head);

    function mergeSort(head) {
        if(head === null || head.next === null) {
            return head;
        }
        let slow = head, fast = head.next.next, left, right;
        while(fast !== null && fast.next !== null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        right = mergeSort(slow.next);
        slow.next = null;
        left = mergeSort(head);
        return mergeList(left, right);
    }
    
    function mergeList(left, right) {
        let curr = new ListNode();
        let dummy = curr;
        while(left !== null && right !== null) {
            if(left.val < right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        if(left !== null) {
            curr.next = left;
        }
        if(right !== null) {
            curr.next = right;
        }
        return dummy.next;
    }
};

234题目描述：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解析：

1.首先运用快慢指针找出中间节点
2.反转中间节点之后的链表
3.分别对比从头节点和反转后链表的节点值

Java：

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = resverse(slow);
        while(fast != null) {
            if(fast.val != head.val) {
                return false;
            }
            head = head.next;
            fast = fast.next;
        }
        return true;
    }
    private ListNode resverse(ListNode head) {
        ListNode curr = head, pre = null;
        while(curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
}

JavaScript:

var isPalindrome = function(head) {
    let fast = head, slow = head;
    while(fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    fast = reverse(slow);
    while(fast !== null) {
        if(fast.val !== head.val) {
            return false;
        }
        fast = fast.next;
        head = head.next;
    }
    return true;
    
    function reverse(head) {
        let curr = head, pre = null;
        while(curr !== null) {
            let temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
};