要實現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鏈表的反轉,分別采用了迭代和遞歸兩種方式。