题解 | #重排链表#

package main
import . "nc_tools"

//时间On，空间O1
func reorderList( head *ListNode )  {
    if head == nil || head.Next == nil {
        return
    }

    mid := midListNode(head)
    l1 := head
    l2 := mid.Next

    l2 = reverseList(l2)
    mid.Next = nil

    mergeList(l1, l2)
}

//1，找中点函数
func midListNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

//2，翻转链表
func reverseList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    //pre := &ListNode{}

    for cur != nil {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    return pre
}

//3.合并链表
func mergeList(l1, l2 *ListNode) {
    for l1 != nil && l2 != nil {
        l1_tmp := l1.Next
        l2_tmp := l2.Next

        l1.Next = l2
        l1 = l1_tmp

        l2.Next = l1
        l2 = l2_tmp
    }
}