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

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

语法

func reorderList(head *Node) {…}

重排链表的函数“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)
}

输出

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

示例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)
}

输出

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

结论

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