Let’s talk about how golang uses recursion to reverse linked lists

In golang, reversing the linked list can be implemented using recursion. In the recursive function, we first need to pass the next node of the current node into the recursive function as a parameter, and then let the current node point to the node next to the next node. Finally, the return value of the recursive function is returned, which is the new head node.

The following is the golang code that uses recursion to reverse the linked list:

type ListNode struct {
    Val int
    Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

We first determine if the head node or the next node of the head node is nil, then return head directly. Otherwise, we call the recursive function, passing in the next node of head. Next, we let the next node of head point to head, and then set the next node of head to nil. Finally, the new head node newHead is returned.

We can use the following test code to verify whether our function is correct:

// 测试代码
func main() {
    node1 := ListNode{Val: 1}
    node2 := ListNode{Val: 2}
    node3 := ListNode{Val: 3}
    node4 := ListNode{Val: 4}
    node5 := ListNode{Val: 5}
    
    node1.Next = &node2
    node2.Next = &node3
    node3.Next = &node4
    node4.Next = &node5
    
    fmt.Println("原链表：")
    printList(&node1)
    newHead := reverseList(&node1)
    fmt.Println("反转后的链表：")
    printList(newHead)
}
func printList(head *ListNode) {
    for p := head; p != nil; p = p.Next {
        fmt.Printf("%d ",p.Val)
    }
    fmt.Println()
}

The running results are as follows:

原链表：
1 2 3 4 5 
反转后的链表：
5 4 3 2 1

As can be seen from the running results, our inversion The linked list function reverseList has successfully reversed the original linked list.

Summary:

This article introduces how to implement the golang code of reversing the linked list through recursive functions. The code to reverse the linked list through a recursive function is concise, easy to understand, and easy to understand. In actual projects, we can choose different methods to implement the reverse linked list according to our needs.

The above is the detailed content of Let’s talk about how golang uses recursion to reverse linked lists. For more information, please follow other related articles on the PHP Chinese website!