温馨提示×

golang链表反转的方法是什么

小亿
119
2024-01-27 17:59:50
栏目: 编程语言

在Golang中,可以使用迭代和递归两种方法来反转链表。

  1. 迭代法: 迭代法是通过遍历链表,逐个改变指针的指向实现链表的反转。

    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
            prev = curr
            curr = next
        }
        return prev
    }
    
  2. 递归法: 递归法是通过递归地反转链表的子链表,并改变相邻节点的指针指向实现链表的反转。

    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
        head.Next = nil
        return newHead
    }
    

无论使用哪种方法,都需要注意处理链表为空或只有一个节点的情况,以及在迭代法中,始终保持对下一个节点的引用。

0