143. 重排链表

题目大意：给定一个单链表 L：L_0→_L_1→…→_Ln-1→L_n ，
将其重新排列后变为： _L_0→_Ln→L_1→_Ln-1→L_2→_Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

整体思路：
1、快慢指针找到中间节点
2、反转后半段链表
3、合并前半段链表和后半段链表
方法一：寻找链表中点 + 链表逆序 + 合并链表。综合考察代码能力
复杂度分析

  • 时间复杂度：O(N)，其中 N是链表中的节点数。
  • 空间复杂度：O(1)。
  1. //简化版本
  2. //绝杀考点，1,快慢指针找到中点，2,然后后半段翻转，3,再二路归并
  3. func reorderList(head *ListNode) {
  4.     if head == nil || head.Next == nil {
  5.         return 
  6.     }
  8.     mid := middleNode(head)
  9.     l1 := head
  10.     l2 := mid.Next
  12.     l2 = reverseList(l2)
  13.     mid.Next = nil 
  15.     mergeList(l1,l2)l
  16. }
  18. //1，找中点函数
  19. func middleNode(head *ListNode) *ListNode {
  20.     slow, fast := head, head
  21.     for fast.Next != nil && fast.Next.Next != nil {
  22.         slow = slow.Next
  23.         fast = fast.Next.Next
  24.     }
  25.     return slow
  26. }
  28. //2，翻转链表
  29. func reverseList(head *ListNode) *ListNode {
  30.     cur := head
  31.     var pre *ListNode = nil
  33.     for cur != nil {
  34.         temp := cur.Next
  35.         cur.Next = pre
  36.         pre = cur
  37.         cur = temp
  38.     }
  39.     return pre
  40. }
  42. //3.合并链表
  43. func mergeList(l1, l2 *ListNode) {
  45.     for l1 != nil && l2 != nil {
  46.         l1_tmp := l1.Next
  47.         l2_tmp := l2.Next
  49.         l1.Next = l2
  50.         l1 = l1_tmp
  52.         l2.Next = l1
  53.         l2 = l2_tmp
  54.     }
  55. }
//绝杀考点，1,快慢指针找到中点，2,然后后半段翻转，3,再二路归并

//1，中点函数，找的是双数中的前数，单数本身
func middleNode(head *ListNode) *ListNode {
    slow , fast := head , head
    for fast.Next != nil && fast.Next.Next != nil {     //fast.Next != nil 是后数
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

//2，翻转链表
func reverseList(head *ListNode) *ListNode {

    //var cur *ListNode = head
    var pre *ListNode = nil //定义哑结点链表的又一种模板
    cur := head

    for cur != nil {
        temp := cur.Next    
        cur.Next = pre      //只翻转指针指向，不翻转节点！
        pre = cur
        cur = temp
    }
    return pre
}

//3,合并链表
func mergeList(l1, l2 *ListNode) {
    var l1_tmp, l2_tmp *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
    }
}

func reorderList(head *ListNode) {
    if head == nil {
        return                     //返回值不写，啥意思？
    }

    mid := middleNode(head)
    l1 := head
    l2 := mid.Next
    l2 = reverseList(l2)
    mid.Next = nil                 // 断掉前一半链表的最后指向，免得出现环
    mergeList(l1,l2)            //核心函数，给我归并。。。
}

方法二：线性表

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。
因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。
复杂度分析

  • 时间复杂度：O(N)，其中 N 是链表中的节点数。

  • 空间复杂度：O(N)，其中 N是链表中的节点数。主要为线性表的开销。

    //2.线性表存储
func reorderList(head *ListNode) {
  if head == nil {
      return 
  }
  nodes := []*ListNode{}                         //定义一个空的线性表
  for node := head; node != nil ; node = node.Next {
      nodes = append(nodes, node)             //线性表的存储 模板
  }

  i := 0  //得先赋值i，不然后面调用不了 nodes[i].Next
  j := len(nodes) - 1
  for i = 0; i < j ; i++ {
      if i != j {
          nodes[i].Next = nodes[j]                //迭代的走Z字型
          nodes[j].Next = nodes[i+1]
          j--                                  //重要的靠近指针
      }
  }
  nodes[i].Next = nil                         //指向空，不用管，单数就符合；
                                              //双数就倒数第二个 两个指向，一个为空就行。画图
}

    方法三：头尾放一起，中间递归 ```go //方法三，递归 func reorderList(head *ListNode) { if head == nil || head.Next == nil || head.Next.Next == nil {

      return

    } var len int // 计算链表长度 tmp := head for tmp != nil {

      len++
  tmp = tmp.Next

    } // 开始递归 reorderListHelper(head, len) }

func reorderListHelper(head ListNode, len int) ListNode{ var upTail *ListNode // 返回上一层(外一层)的 尾结点 // 终止条件 旋转到中心 if len == 1 { upTail = head.Next head.Next = nil return upTail } if len == 2 { upTail = head.Next.Next head.Next.Next = nil return upTail } tail := reorderListHelper(head.Next, len - 2) // head.Next 为往里一层 及剩余节点数量 返回值为外一层的尾结点 // 当前层的头结点 为head // 先记录要返回当前层 的 外一层的尾结点 就是当前层的尾结点 向后一个 upTail = tail.Next // 记录里一层的头结点 用于连接 inHead := head.Next // 当前层的连接 head.Next = tail // 当前层尾结点 连接里面一层 头结点 tail.Next = inHead return upTail }

```