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:

• Define three pointers: prev, head, next
• Traverse the linked list and point the next pointer of head to prev
• Point the prev pointer to head
• Point head to next
• Repeat the above steps until head is empty

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:

• Recurse to the end of the linked list
• Point the next node of the node to the penultimate node
• Put the penultimate node The next points of the two nodes point to null
• Repeat the above steps until the head node of the original linked list is returned

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!