题解 | #重排链表#

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return void
*/
func reorderList( head *ListNode )  {
    // write code here
    if head == nil || head.Next == nil || head.Next.Next == nil{
        return 
    }
    
    mid := midList(head)
    l1 := head
    l2 := mid.Next
    mid.Next = nil  //找中位 分为两半的链表
    
    l2 = reverseList(l2)  //反转后半段
   
    mergeList(l1,l2)  //两个链表一对一合并
}

//找中位数
func midList( head *ListNode ) *ListNode {
    slow , fast := head,head
    for  fast != nil && fast.Next != nil{
        slow  = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

//反转链表
func reverseList( head *ListNode ) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    last := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}

//合并链表
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
    }
}