golang linked list reversal

Golang is one of the most popular programming languages ​​currently. Its simplicity and efficiency are deeply loved by developers. In Golang, linked lists are widely used in various data structures. However, the operation of linked lists is relatively complex, and special attention needs to be paid to the correctness of pointer operations. In this article, we will discuss how to reverse a linked list using Golang.

What is a linked list?

In computer science, a linked list is a data structure that is a collection of nodes. Each node contains data and a pointer to the next node. Its characteristic is that it can insert and delete nodes efficiently, but randomly accessing a node requires traversing the entire linked list.

The data structure of the linked list is as follows:

type Node struct {
    data int
    next *Node
}

where data is the data stored in the node, and next is the pointer to the next node. When next is equal to nil, it means that this is the last node of the linked list.

Traversal and insertion operations of linked lists

The basic operation of traversing a linked list is to traverse from the head node of the linked list to the tail node of the linked list. During the traversal process, certain operations can be performed on each node, such as outputting the value of the node. The following is an example of traversing a linked list:

func printList(head *Node) {
    p := head
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
}

For the insertion operation, we need to first find the position to be inserted, and then modify the pointer pointing. For example, insert a new node after the third node of the linked list, the code is as follows:

func insert(head *Node, pos int, value int) *Node {
    p := head
    for i := 1; i < pos && p != nil; i++ {
        p = p.next
    }
    if p == nil {
        return head
    }
    newNode := &Node{data: value}
    newNode.next = p.next
    p.next = newNode
    return head
}

Reversal of the linked list

Reversing the linked list means to reverse the order of the nodes in the linked list, that is, the original The first node becomes the last node, and the original last node becomes the first node. The process of reversing a linked list involves reversing the pointers between nodes in the linked list. The following is the implementation code for inverting the linked list:

func reverseList(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    var prev *Node
    curr := head
    for curr != nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

First, we determine whether the linked list is empty or has only one node. In this case, there is no need to reverse it and the original linked list head node is returned directly. Then we define two pointers, prev points to the previous node of the current node, and curr points to the current node. We traverse the linked list starting from the head node, each loop points the next pointer of the current node to its previous node, and then moves the prev and curr pointers backward one nodes until the entire linked list is traversed. Finally, the reversed list head node is returned.

The test code is as follows:

func main() {
    head := &Node{data: 1}
    head.next = &Node{data: 2}
    head.next.next = &Node{data: 3}
    head.next.next.next = &Node{data: 4}
    fmt.Println("Original list:")
    printList(head)
    head = reverseList(head)
    fmt.Println("
Reversed list:")
    printList(head)
}

The output result is:

Original list:
1 2 3 4
Reversed list:
4 3 2 1

Summary

This article introduces the basic operations of linked lists in Golang and how to reverse linked lists. Although the operation of linked lists is slightly complicated, it has the advantages of efficient insertion and deletion, and is widely used in various scenarios. When using linked lists, special attention needs to be paid to the correctness of pointers to avoid problems such as memory leaks.

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