什么是递归？|极客笔记

什么是递归？

递归是一种算法的设计方法，指的是函数自己调用自己。递归是解决一类问题的有力工具，可以很好地表达复杂的问题。递归可以将一个问题简化为一个更小的问题，直到简化为一个问题的解决方法已知或者变得简单。

什么是链表？

链表是一种数据结构，是指在每一个节点邻接关系指示下一个节点的链式结构。每一个节点包含了存储数据和指向下一个节点的指针。

链表有很多种不同的类型，如单向链表、双向链表、环形链表等。不同类型的链表之间最大的区别就是每个节点的指针所指向的下一个节点是否可以是其前面的节点。

思路

给定一个单向链表，每次将链表的第一个节点插入到最后，直到链表为空。这个过程实际上就是重排链表的过程。例如，对于链表 1 -> 2 -> 3 -> 4 -> 5，经过重排后变为 1 -> 5 -> 2 -> 4 -> 3。

因为每次需要找到链表中最后一个节点，而链表是单向的，因此暴力的思路是每次都要从头开始遍历整个链表，时间复杂度会很高。此时，需要用到递归来简化问题。

定义一个递归函数 recur，将问题简化为将给定链表的首节点接在已经完成重排的子链表之后，然后依次递归剩余的节点，直到链表为空。

具体来说，每次递归处理的节点分为两个部分：

链表的首节点
已经处理完毕的子链表

在递归函数中，如果当前链表为空，则递归终止，直接返回。否则，将链表的首节点接在已经完成重排的子链表之后，然后将处理好接好的子链表作为递归的返回值。

接下来，看看具体实现。

代码实现

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}
    reorderList(head)
    for head != nil {
        fmt.Print(head.Val, " -> ")
        head = head.Next
    }
    fmt.Println("nil")
}

func reorderList(head *ListNode) {
    recur(head)
}

func recur(node *ListNode) *ListNode {
    // 递归终止条件
    if node == nil || node.Next == nil || node.Next.Next == nil {
        return node
    }
    tail := getTail(node)
    next := node.Next
    node.Next = tail
    tail.Next = recur(next)
    return node
}

func getTail(node *ListNode) *ListNode {
    prev := node
    for node.Next != nil {
        prev = node
        node = node.Next
    }
    prev.Next = nil
    return node
}