重排链表

题目描述：

给定一个单链表 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.

思路:

用快慢指针，找到链表的中间结点，让后面的结点逆置，然后后面的结点一个个插入

代码:

func reorderList(head *ListNode)  {
    if head==nil||head.Next==nil{
        return
    }
    var fast,slow,head2,pre *ListNode
    fast,slow=head,head
    for fast!=nil&&fast.Next!=nil{
        fast=fast.Next.Next
        pre = slow
        slow=slow.Next
    }

    pre.Next=nil
    head2=nil
    for slow!=nil{
        tmp := slow.Next
        slow.Next=head2
        head2=slow
        slow=tmp
    }

    //fmt.Println(head2.Val,head2.Next.Val)
    true_head := head
    for head.Next!=nil{
        tmp:=head2.Next
        head2.Next=head.Next
        head.Next=head2
        head=head2.Next
        head2=tmp
    }
  
    if head2!=nil{
        head.Next=head2
    }
    head=true_head
}

代码效率：

执行用时：12 ms, 在所有 Go 提交中击败了76.58%的用户
内存消耗：5.3 MB, 在所有 Go 提交中击败了79.64%的用户