反转链表之递归

递归的写法总是使人眼前一亮，总是让人满口称赞，正常也写不出那么优美的递归。

递归首先一点需要明确递归函数的定义（函数作用、参数、返回值）和递归的出口。

labuladong 一直在强调不要跳进递归，不要跳进递归。因为人脑是思考不了那么复杂的堆栈逻辑，人脑擅长高屋建瓴去思考函数定义，而不是底层逻辑。

反转整个链表

// 反转整个链表
func reverseAll(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    // 继续反转下个节点
    newHead := reverseAll(head.Next)
    // 递归调用到最后，最后一个节点就是新的头结点

    //【1】 1 -> 2 -> 3 -> 4 -> 5
    //【2】 1 <-> 2 <- 3 <- 4 <- 5
    //【3】 nil <-1 <- 2 <- 3 <- 4 <- 5
    head.Next.Next = head // 这里 head 还是当前节点， head.Next => 2 ，让 2 的next 指向 当前节点 1
    head.Next = nil       // 切断当前节点的下个指针
    return newHead
}

func TestReverseAll(t *testing.T) {
    t.Log(reverseAll(GenerateLists(1, 2, 3, 4)))
}

反转链表前 K 个节点

func reverseK(head *ListNode, k int) *ListNode {
    var lastNext *ListNode // 头节点的下个节点需要记住，否则后面连不起来
    var reverse func(head *ListNode, k int) *ListNode
    reverse = func(head *ListNode, k int) *ListNode {
        if k == 1 {
            lastNext = head.Next
            return head
        }

        last := reverse(head.Next, k-1)

        head.Next.Next = head
        head.Next = lastNext // 和 reverseAll 的区别在于 这里的 head 指针指向上面切断节点
        return last
    }
    return reverse(head, k)
}

func TestReverseK(t *testing.T) {
    t.Log(reverseK(GenerateLists(1, 2, 3, 4, 5), 3))
}

反转链表 M 到 N 个节点

func reverseMN(head *ListNode, m, n int) *ListNode {
    if m == 1 {
        return reverseK(head, n) //
    }

    head.Next = reverseMN(head.Next, m-1, n-1)
    return head
}

func TestReverseMN(t *testing.T) {
    t.Log(reverseMN(GenerateLists(1, 2, 3, 4, 5, 6, 7), 2, 4))
}

我的辅助函数

// ListNode ListNode
type ListNode struct {
    Val  int
    Next *ListNode
}

func (head *ListNode) String() string {
    cur := head

    arr := []string{}
    for cur != nil {
        arr = append(arr, strconv.Itoa(cur.Val))
        cur = cur.Next
    }
    return strings.Join(arr, ",")
}

// GenerateList GenerateList
func GenerateList(arr []int) *ListNode {
    head := &ListNode{
        Val: -1,
    }

    current := head
    for i := 0; i < len(arr); i++ {
        current.Next = &ListNode{
            Val: arr[i],
        }
        current = current.Next
    }

    return head.Next
}

// GenerateLists GenerateLists
func GenerateLists(arr ...int) *ListNode {
    return GenerateList(arr)
}