Reverse linked list golang

Reversing the linked list is a classic data structure algorithm problem, which requires operating nodes on the linked list, reversing the linked list and returning the reversed head node.

Using golang language to implement a reverse linked list can effectively demonstrate golang's object-oriented and pointer operation features. Let's explain in detail how to implement a reverse linked list.

1. Define the linked list node structure

First, we need to define a linked list node structure, which contains two member variables: value and pointer to the next node.

type ListNode struct {
    Val int
    Next *ListNode
}

2. Reverse the linked list

Next, we have to write a function to reverse the linked list. This function will traverse the linked list and reverse the next pointer of each node to the previous node, and finally return the reversed head node.

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

This function contains a pointer prev, which is used to maintain the previous node during the traversal process.

First, we initialize the prev pointer to empty, indicating that it is located before the first node of the linked list.

Then we start traversing the linked list.

In each loop, we use an additional pointer temp to temporarily store the next node of the current node.

Next, we reverse the next pointer of the current node to the prev pointer, and insert the current node into the position pointed by the prev pointer.

Finally, we point the current node to temp so that we can traverse it in the next loop.

3. Test the reverse linked list

Through the above code, we have completed the implementation of the reverse linked list. Next, we can write some test code to verify whether our reverse linked list function is correct.

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}
    fmt.Println("Original List: ")
    printList(head)
    reversedList := reverseList(head)
    fmt.Println("Reversed List: ")
    printList(reversedList)
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

In this test function, we first created a linked list with 5 nodes and printed out the initial order of the linked list. Then we called the reverseList() function to reverse the linked list and output the reverse. The last linked list. At the end, we define a printList() function to print the linked list.

Run the above test function, we can get the following results:

Original List: 
1 2 3 4 5 
Reversed List: 
5 4 3 2 1 

As can be seen from the results, we successfully reversed the linked list.

Summary

Reversing a linked list is a very interesting and common algorithm problem, and it is often used in practical applications.

Through this article, we learned how to implement a reverse linked list on golang, and used golang's object-oriented and pointer operation features.

By implementing this algorithm ourselves, we can better understand the data structure of the linked list, and at the same time further deepen our mastery of the golang language.

The above is the detailed content of Reverse linked list golang. For more information, please follow other related articles on the PHP Chinese website!