143. 重排链表

题意：

解题思路：

思路：
1.找到链表的中点
2.以中点分割链表为2部分
3.反转分割的右链表
4.将左右链表依次拼接

图示：

PHP代码实现：

/*
 * @lc app=leetcode.cn id=143 lang=php
 *
 * [143] 重排链表
 *
 * https://leetcode-cn.com/problems/reorder-list/description/
 *
 * algorithms
 * Medium (52.13%)
 * Likes:    140
 * Dislikes: 0
 * Total Accepted:    14.1K
 * Total Submissions: 26.1K
 * Testcase Example:  '[1,2,3,4]'
 *
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 
 * 示例 1:
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 */
// @lc code=start
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return NULL
     */
    function reorderList($head) {
        $slow = $head;
        $fast = $head;
        while ($fast->next != null && $fast->next->next != null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $newHead = $slow->next;
        $slow->next = null;
        $newHead = $this->reverseList($newHead);
        while ($newHead != null) {
            $tmp = $newHead->next;
            $newHead->next = $head->next;
            $head->next = $newHead;
            $head = $newHead->next;
            $newHead = $tmp;
        }
    }
    function reverseList($head) {
        if ($head == null || $head->next == null) return $head;
        $p = $this->reverseList($head->next);
        $head->next->next = $head;
        $head->next = null;
        return $p;
    }
}
// @lc code=end

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil {
        return 
    }
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast, slow = fast.Next.Next, slow.Next
    }
    newHead := slow.Next
    slow.Next = nil //分割两个链表
    newHead = reverse(newHead) // 反转中点以后的链表
    // 将两个链表拼接
    for newHead != nil {
        tmp := newHead.Next
        newHead.Next = head.Next
        head.Next = newHead
        head, newHead = newHead.Next, tmp
    }
}
func reverse(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    p := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return p
}