文心一言 VS 讯飞星火 VS chatgpt （114）-- 算法导论10.2 7题

七、用go语言，给出一个 O(n)时间的非递归过程，实现对一个含 n个元素的单链表的逆转。要求除存储链表本身所需的空间外，该过程只能使用固定大小的存储空间。

文心一言：

在Go语言中，你可以使用迭代方法来反转一个单链表。这种方法只需要O(1)的额外空间。首先，我们需要定义链表的数据结构：

type ListNode struct {

Val  int

Next *ListNode

}

然后，我们可以使用以下代码来反转一个链表：

func reverseList(head *ListNode) *ListNode {

var prev *ListNode

curr := head

for curr != nil {

nextTemp := curr.Next //保存下一个节点

curr.Next = prev      //反转链接

prev = curr           //后移

curr = nextTemp        //后移

}

return prev

}

这个函数会迭代链表的每个节点，并改变当前节点的Next指针以指向它的前一个元素。由于我们需要在更改指针之前保存下一个节点，所以我们需要在更改指针之前将当前节点的Next指针保存到临时变量中。

在更改指针后，我们将当前节点和下一个节点向后移动，因此我们可以在O(1)的空间中反转链表。这个函数的时间复杂度是O(n)，因为它需要遍历链表的每个节点。

在这里插入图片描述在这里插入图片描述讯飞星火：

package main

import "fmt"

type ListNode struct {

Val  int

Next *ListNode

}

func reverseList(head *ListNode) *ListNode {

var prev *ListNode

current := head

for current != nil {

nextTemp := current.Next

current.Next = prev

prev = current

current = nextTemp

}

return prev

}

func main() {

// 创建链表：1 -> 2 -> 3 -> 4 -> 5

head := &ListNode{Val: 1}

head.Next = &ListNode{Val: 2}

head.Next.Next = &ListNode{Val: 3}

head.Next.Next.Next = &ListNode{Val: 4}

head.Next.Next.Next.Next = &ListNode{Val: 5}

// 逆转链表

newHead := reverseList(head)

// 打印逆转后的链表：5 -> 4 -> 3 -> 2 -> 1

current := newHead

for current != nil {

fmt.Printf("%d -> ", current.Val)

current = current.Next

}

fmt.Println("nil")

}

在这里插入图片描述在这里插入图片描述360智脑：

以下是一个使用go语言实现对单链表进行逆转的O(n)时间非递归过程:

package main

import "fmt"

// 定义链表节点结构体

type ListNode struct {

Val  int

Next *ListNode

}

// 定义链表类

class List {

constructor() {}

reverseList(head: *ListNode) -> *ListNode {

var prev *ListNode = head

var current *ListNode = head.Next

while current != nil {

var next *ListNode = current.Next

current.Next = prev

prev = current

current = next

}

head.Next = prev

return head

}

}

// 测试

var list = new List()

list.add(1)

list.add(2)

list.add(3)

list.add(4)

list.add(5)

fmt.Println("原链表:")

printList(list.head)

list.reverseList(&list.head)

fmt.Println("逆转后的链表:")

printList(list.head)

其中，List是链表类，reverseList是反转链表的方法。在reverseList方法中，我们使用两个指针prev和current分别指向链表的头节点和当前节点，然后遍历整个链表，每次将当前节点的下一个节点赋值给当前节点，并将当前节点的指针指向前一个节点，最后返回头节点即可。

在这里插入图片描述

在这里插入图片描述智谱清言：

package main

import (

"fmt"

)

type ListNode struct {

Val  int

Next *ListNode

}

func reverseList(head *ListNode) *ListNode {

var prev *ListNode

current := head

for current != nil {

nextTemp := current.Next

current.Next = prev

prev = current

current = nextTemp

}

return prev

}

func printList(head *ListNode) {

for head != nil {

fmt.Print(head.Val, "->")

head = head.Next

}

fmt.Println("nil")

}

func main() {

head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}}}}

fmt.Println("Original list:")

printList(head)

reversedHead := reverseList(head)

fmt.Println("Reversed list:")

printList(reversedHead)

}

这个程序首先定义了一个ListNode结构体，用于表示链表的节点。reverseList函数接受一个链表的头节点作为参数，并返回逆转后的链表的头节点。

在reverseList函数中，我们使用了一个前置节点prev，初始值为nil。我们从链表的头节点开始，遍历链表的每个节点。对于每个节点，我们保存其下一个节点（nextTemp），然后将当前节点的前置节点设置为prev，将当前节点设置为下一个节点，继续遍历。当遍历到链表的尾部时，current和nextTemp都为nil，此时我们将prev作为链表的新头节点返回。

printList函数用于打印链表。我们在main函数中创建了一个示例链表，然后调用reverseList函数对其进行逆转，并打印原始链表和逆转后的链表。

在这里插入图片描述

在这里插入图片描述通义千问：

以下是使用Go语言实现的非递归方法，用于逆转一个含n个元素的单链表：

package main

import "fmt"

type ListNode struct {

Val int

Next *ListNode

}

func reverseList(head *ListNode) *ListNode {

prev := nil

curr := head

for curr != nil {

next := curr.Next

curr.Next = prev

prev = curr

curr = next

}

return prev

}

func main() {

head := &ListNode{Val: 1}

head.Next = &ListNode{Val: 2}

head.Next.Next = &ListNode{Val: 3}

head.Next.Next.Next = &ListNode{Val: 4}

head.Next.Next.Next.Next = &ListNode{Val: 5}

fmt.Println("Original List:")

for curr := head; curr != nil; curr = curr.Next {

fmt.Printf("%d ", curr.Val)

}

newHead := reverseList(head)

fmt.Println("\nReversed List:")

for curr := newHead; curr != nil; curr = curr.Next {

fmt.Printf("%d ", curr.Val)

}

}

在这个程序中，我们使用三个指针：prev，curr和next。prev指针初始化为nil，curr指针初始化为链表的头节点。然后，我们进入一个循环，该循环在curr不为nil时继续运行。在每次迭代中，我们都做以下操作：

1.将next指针设置为curr的下一个节点。

2.将curr的next指针设置为prev。

3.将prev和curr向前移动一位。

当我们完成循环时，prev指针将指向逆转后的链表的头节点。我们返回prev指针，这就是逆转后的链表的头节点。

注意，这个程序使用了常数大小的额外空间。

在这里插入图片描述

在这里插入图片描述天工：

以下是使用 Go 语言实现 O(n) 时间复杂度的非递归方式逆转单链表的代码：

func reverseList(head *ListNode) *ListNode {

var prev *ListNode = nil

var curr *ListNode = head

for curr != nil {

next := curr.Next

curr.Next = prev

prev = curr

curr = next

}

return prev

}

该代码中，我们使用了三个指针，分别是prev、curr和next。其中，prev指向当前节点的前一个节点，curr指向当前节点，next指向当前节点的下一个节点。我们从头节点开始遍历链表，每次将当前节点的next指针指向prev，然后更新prev和curr的值，继续遍历下一个节点。最后返回prev即可。

由于我们只需要常量级别的额外空间，因此空间复杂度为 O(1)。时间复杂度为 O(n)，因为我们需要遍历整个链表一次。

在这里插入图片描述chatgpt：

下面是一个使用Go语言实现对单链表逆转的非递归过程，时间复杂度为O(n)：

package main

import "fmt"

type ListNode struct {

Val  int

Next *ListNode

}

func reverseList(head *ListNode) *ListNode {

var prev *ListNode

current := head

for current != nil {

next := current.Next

current.Next = prev

prev = current

current = next

}

return prev

}

func displayList(head *ListNode) {

current := head

for current != nil {

fmt.Printf("%d ", current.Val)

current = current.Next

}

fmt.Println()

}

func main() {

// 创建一个示例链表 1 -> 2 -> 3 -> 4 -> 5

head := &ListNode{Val: 1}

node2 := &ListNode{Val: 2}

node3 := &ListNode{Val: 3}

node4 := &ListNode{Val: 4}

node5 := &ListNode{Val: 5}

head.Next = node2

node2.Next = node3

node3.Next = node4

node4.Next = node5

fmt.Println("原链表：")

displayList(head)

reversedHead := reverseList(head)

fmt.Println("逆转后的链表：")

displayList(reversedHead)

}

这段代码定义了一个ListNode结构体来表示单链表节点，然后实现了reverseList函数来对单链表进行逆转。过程中使用了三个指针：prev用于表示当前节点的前一个节点，current用于表示当前节点，next用于保存下一个节点。我们对每个节点进行处理，将当前节点的下一个节点指向前一个节点，然后更新prev、current和next指针。最后返回逆转后的链表的头节点。

在main函数中，创建了一个示例链表，并调用reverseList函数对其进行逆转。最后调用displayList函数来打印原链表和逆转后链表的值，以验证结果。

这个过程的空间复杂度为O(1)，除了存储链表本身所需的空间外，只使用了固定大小的三个指针。

在这里插入图片描述

在这里插入图片描述