要实现golang链表的反转,可以采用迭代的方式或者递归的方式。
迭代方式的代码如下:
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode // 上一个节点
curr := head // 当前遍历的节点
for curr != nil {
next := curr.Next // 保存下一个节点
curr.Next = prev // 将当前节点的Next指向上一个节点
prev = curr // 更新上一个节点为当前节点
curr = next // 更新当前节点为下一个节点
}
return prev // 返回反转后的头节点
}
递归方式的代码如下:
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next) // 先反转后面的链表
head.Next.Next = head // 将当前节点的下一个节点的Next指向当前节点,实现反转
head.Next = nil // 将当前节点的Next置为nil,防止形成环
return newHead // 返回新的头节点
}
以上代码实现了golang链表的反转,分别采用了迭代和递归两种方式。