Home > Article > Backend Development > golang singly linked list inversion
Preface
In computer science, a linked list is a basic data structure that consists of a series of nodes that are linked to each other through pointers. Linked lists can easily implement insertion and deletion operations, but the performance of access operations is relatively poor because traversal is required to find elements. This article will introduce how to use Golang to implement the inversion algorithm of a singly linked list.
Definition of singly linked list
In Golang, we can use structures to define singly linked lists. Define a structure Node, which represents the node of a singly linked list, which contains the value val of the node and its pointer next pointing to the position of the next node.
type Node struct { val int next *Node }
Define a head pointer, pointing to the head node of the linked list. If the linked list is empty, head points to nil.
var head *Node = nil
Initialization of singly linked list
In Golang, we can use the new function to allocate the memory of a node and return the pointer of the node.
func newNode(val int) *Node { return &Node{ val, nil, } }
Creating a singly linked list can be achieved by continuously adding nodes using newNode. Taking linked lists 1, 2, and 3 as an example, the code is as follows:
node1 := newNode(1) node2 := newNode(2) node3 := newNode(3) node1.next = node2 node2.next = node3 head = node1
Inversion of a singly linked list
There are two methods to achieve the inversion of a singly linked list: iteration and recursion.
Method 1: Iteration
The core idea of the iteration method is to traverse the linked list and point the pointer of the current node to the previous node to achieve the purpose of reversal.
The specific implementation process is as follows:
The Golang implementation code is as follows:
func reverseList1(head *Node) *Node { var prev *Node = nil var next *Node = nil for head != nil { next = head.next head.next = prev prev = head head = next } return prev }
Method 2: Recursion
The core idea of the recursive method is to recurse to the end of the linked list first, and then return to the traversed nodes in reverse order.
The specific implementation process is as follows:
The Golang implementation code is as follows:
func reverseList2(head *Node) *Node { if head == nil || head.next == nil { return head } newHead := reverseList2(head.next) head.next.next = head head.next = nil return newHead }
The complete code is as follows:
package main import ( "fmt" ) type Node struct { val int next *Node } func newNode(val int) *Node { return &Node{ val, nil, } } var head *Node func reverseList1(head *Node) *Node { var prev *Node = nil var next *Node = nil for head != nil { next = head.next head.next = prev prev = head head = next } return prev } func reverseList2(head *Node) *Node { if head == nil || head.next == nil { return head } newHead := reverseList2(head.next) head.next.next = head head.next = nil return newHead } func main() { node1 := newNode(1) node2 := newNode(2) node3 := newNode(3) node1.next = node2 node2.next = node3 head = node1 fmt.Println("原链表:") for head != nil { fmt.Printf("%d->", head.val) head = head.next } head = node1 head = reverseList1(head) fmt.Println(" 迭代法倒转后的链表:") for head != nil { fmt.Printf("%d->", head.val) head = head.next } head = node1 head = reverseList2(head) fmt.Println(" 递归法倒转后的链表:") for head != nil { fmt.Printf("%d->", head.val) head = head.next } }
The running results are as follows:
原链表: 1->2->3-> 迭代法倒转后的链表: 3->2->1-> 递归法倒转后的链表: 3->2->1->
Conclusion
This article introduces how to use Golang to implement the inversion of a singly linked list, and introduces two different implementation methods: iteration and recursion . I believe that through studying this article, everyone has mastered the core ideas of these two methods and can flexibly apply them to actual development.
The above is the detailed content of golang singly linked list inversion. For more information, please follow other related articles on the PHP Chinese website!