Example demonstrates how golang implements linked list reversal

Linked list inversion is a classic algorithm problem and a very important knowledge point in data structures and algorithms. Linked list inversion can be widely used in practice and interviews, so it is very necessary for programmers to master the linked list inversion algorithm.

It is also very simple to implement the linked list reversal algorithm in Go language. Below we will demonstrate how to implement the linked list reversal algorithm.

1. Basics of linked lists

First of all, let’s briefly introduce the basic knowledge of linked lists. A linked list is a non-linear data structure that consists of multiple nodes. Each node has two properties: one that stores the value of the data element, and another that is a pointer to the next node.

Linked lists have many advantages over arrays. For example, elements can be added or deleted dynamically without knowing the number of elements stored in the linked list in advance.

A simple linked list node can be defined as:

type ListNode struct {
    Val  int
    Next *ListNode
}

In this definition, Val is the value stored in this node, Next is a Pointer to the next node. If this node is the last one in the linked list, Next points to nil.

The head node of the linked list represents the beginning of the linked list, often also called "sentinel node" or "virtual node". It doesn't store any value, just points to the first actual node.

2. Linked list reversal algorithm

Now we begin to explain the implementation of the linked list reversal algorithm. The basic idea of ​​the linked list reversal algorithm is to traverse the entire linked list, reverse the direction of the pointer of each node, and finally point the head node to the tail node of the original linked list to complete the reversal of the entire linked list.

The key process of the linked list reversal algorithm is the reversal of the pointer of each node. The specific implementation method is as follows:

// 将链表反转
func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode
    cur = head
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

The core of this algorithm is the definition of two pointersprev and cur represent the previous node and the current node respectively. Traverse the entire linked list starting from the head node, exchanging the points of the prev and cur pointers each time, while letting cur point to the next node.

3. Testing

Finally, we can verify whether our code is correct through some test cases.

func main() {
    // 初始化一个链表
    n1 := &ListNode{Val: 1}
    n2 := &ListNode{Val: 2}
    n3 := &ListNode{Val: 3}
    n4 := &ListNode{Val: 4}
    n1.Next = n2
    n2.Next = n3
    n3.Next = n4
    // 打印原链表
    printList(n1)
    // 反转链表
    newHead := reverseList(n1)
    // 打印反转后的链表
    printList(newHead)
}

// 打印链表
func printList(head *ListNode) {
    p := head
    for p != nil {
        fmt.Printf("%d -> ", p.Val)
        p = p.Next
    }
    fmt.Println("nil")
}

Output:

1 -> 2 -> 3 -> 4 -> nil
4 -> 3 -> 2 -> 1 -> nil

4. Summary

Linked list reversal is a very classic algorithm problem. This article introduces how to implement linked lists in Go language Invert the algorithm. By learning this algorithm, we further consolidate and deepen our understanding of linked lists and pointers.

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