An article explains how to implement reverse linked list in golang

Question: Reversing a singly linked list.

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

First of all, let’s get to know the data structure of the linked list:

There are two elements in the linked list node:

• Value
• Pointer

type ListNode struct {
    Val  int
    Next *ListNode
}

Next points to the next node

Then this question is actually to point the pointer to the previous node

##4->3->2->1->nil55->4->3->2->1->nil

Number of position changes	pre	cur	whole
0	nil	1->2->3->4->5	1->2->3->4->5
1	1->nil	2->-3>->4->5	2->3->4->5->1->nil
2	2->1->nil	3->4->5	3->4->5->2->1->nil
3	3->2->1->nil	4->5	4->5->3 ->2->1->nil
4

You can see it

pre is the frontmost element of cur (pre = cur)
• cur is the linked list element behind the current position (cur = cur.Next)
• cur .Next must be connected to pre (cur.Next = pre)

Full code:

package main

import "fmt"

//链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

//反转链表的实现
func reversrList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre //这句话最重要
    }
    return pre
}

func main() {
    head := new(ListNode)
    head.Val = 1
    ln2 := new(ListNode)
    ln2.Val = 2
    ln3 := new(ListNode)
    ln3.Val = 3
    ln4 := new(ListNode)
    ln4.Val = 4
    ln5 := new(ListNode)
    ln5.Val = 5
    head.Next = ln2
    ln2.Next = ln3
    ln3.Next = ln4
    ln4.Next = ln5

    pre := reversrList(head)
    fmt.Println(pre)
}

For more golang related technical articles, please visit

golangTutorial column!

The above is the detailed content of An article explains how to implement reverse linked list in golang. For more information, please follow other related articles on the PHP Chinese website!