当前位置：极客教程 > Go 语言 > Go 实例 > 使用递归重排链表的 Golang 程序

使用递归重排链表的 Golang 程序

使用递归重排链表的 Golang 程序

链表是一种数据结构，由一组节点组成，每个节点包含一个值和指向列表中下一个节点的指针。在这篇 Golang 文章中，我们将学习如何使用递归重排链表，以及一些辅助函数。

语法

func reorderList(head *Node) {…}
Go

重排链表的函数“reorderList()”使用递归。它以头节点的指针为参数。

算法

  • 第 1 步 − 首先，我们需要导入 fmt 包。

  • 第 2 步 − 现在，创建一个名为 Node 的单个链表节点的结构。它包含两个成员，一个用于保存节点数据值，另一个是指向列表中下一个节点的指针。

  • 第 3 步 − 现在，创建一个名为 reorderList() 的函数，它以链表的头节点作为输入，并修改列表以进行重排。它使用递归来实现这一点。

  • 第 4 步 − 检查链表是否为空或仅包含一个节点，如果是，则无需重新排序。

  • 第 5 步 − 然后，使用 findMiddle 辅助函数使用双指针技术找到链表的中间。

  • 第 6 步 − 接下来，使用 reverselist 辅助函数反转链表的第二部分。它接受第二部分的头，并返回反转后的链表的头。

  • 第 7 步 − 然后，使用 mergeLists 辅助函数合并链表的第一部分和反转后的第二部分。合并后的列表将是已重新排序的列表。

  • 第 8 步 − 最后，将输入链表的头节点更新为已重新排序的列表的头节点。

  • 第 9 步 − 开始 main() 函数。在 main() 函数中，向链表中添加节点。

  • 第 10 步 − 现在，调用 reorderList() 函数对列表进行重新排序，并打印更新后的列表。

  • 第 11 步 − 进一步，通过调用 printList() 函数在屏幕上打印出使用递归更新后的已重新排序的链表。

示例1：使用递归重排链接列表的 Go 程序

在本示例中，我们将使用递归定义 reorderList() 函数，该函数用于重排单向链表。

package main

import "fmt"

type Node struct {
   Val  int
   Next *Node
}

func reorderList(head *Node) {
   if head == nil || head.Next == nil || head.Next.Next == nil {
      return
   }

   fast, slow := head, head
   for fast.Next != nil && fast.Next.Next != nil {
      fast = fast.Next.Next
     slow = slow.Next
   }

   secondHalf := slow.Next
   slow.Next = nil
   var prev *Node
   for secondHalf != nil {
      next := secondHalf.Next
      secondHalf.Next = prev
      prev = secondHalf
      secondHalf = next
   }

   p1, p2 := head, prev
   for p2 != nil {
      next1, next2 := p1.Next, p2.Next
      p1.Next = p2
      p2.Next = next1
      p1, p2 = next1, next2
   }
}

func printList(head *Node) {
   for head != nil {
      fmt.Printf("%d ->", head.Val)
      head = head.Next
   }
   fmt.Println("nil")
}

func main() {
   head := &Node;{Val: 8, Next: &Node;{Val: 7, Next: &Node;{Val: 3, Next: &Node;{Val: 4, Next: nil}}}}
   fmt.Println("Initial Ordered list:")
   printList(head)
   reorderList(head)
   fmt.Println("Updated Reordered list:")
   printList(head)
}
Go

输出

初始有序列表：
8 -> 7 -> 3 -> 4 -> 空
更新后的重新排序列表：
8 -> 4 -> 7 -> 3 -> 空
Go

示例2

在这个示例中，我们将使用递归定义reorderList（）函数，该函数使用帮助函数来重新排序单链表。

package main

import "fmt"

type Node struct {
   Val  int
   Next *Node
}

func reorderList(head *Node) {
   if head == nil || head.Next == nil {
      return
   }

   var prev *Node
   slow, fast := head, head

   for fast != nil && fast.Next != nil {
      prev = slow
      slow = slow.Next
      fast = fast.Next.Next
   }

   prev.Next = nil
   secondHalf := reverseList(slow)

   mergeLists(head, secondHalf)
}

func reverseList(head *Node) *Node {
   if head == nil || head.Next == nil {
      return head
   }

   newHead := reverseList(head.Next)
   head.Next.Next = head
   head.Next = nil

   return newHead
}

func mergeLists(l1, l2 *Node) {
   for l1 != nil {
      l1Next := l1.Next
      l2Next := l2.Next

      l1.Next = l2
      if l1Next == nil {
         break
      }

      l2.Next = l1Next
      l1 = l1Next
      l2 = l2Next
   }
}

func printList(head *Node) {
   for head != nil {
      fmt.Printf("%d ->", head.Val)
      head = head.Next
   }
   fmt.Println("空")
}

func main() {
   head := &Node{Val: 5, Next: &Node{Val: 7, Next: &Node{Val: 3, Next: &Node{Val: 2, Next: &Node{Val: 4, Next: nil}}}}}
   fmt.Println("初始有序列表：")
   printList(head)

   reorderList(head)

   fmt.Println("更新后的重新排序列表：")
   printList(head)
}
Go

输出

初始有序列表：
5 -> 7 -> 3 -> 2 -> 4 -> 空
更新后的重新排序列表：
5 -> 4 -> 7 -> 2 -> 3 -> 空
Go

结论

我们已经成功编译和执行了一个使用递归方法和两个示例的带有一些帮助函数的go语言程序来重新排序列表。在第一个示例中，我们使用了递归方法，在第二个示例中，我们使用了递归方法和帮助函数。

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

Go语言 精品教程

登录

找回密码？

注册