反轉部分鍊錶golang

反轉鍊錶是一個經典的問題，應用廣泛，時間複雜度不高，實現起來也不難。本篇文章將介紹如何在golang中實作一個反轉部分鍊錶的演算法。

反轉鍊錶

先來看看如何反轉鍊錶，我們可以用迭代或遞歸兩種方式來實作。

1. 迭代方式

我們用三個指標pre、cur、next來迭代地進行反轉操作，其中pre和next是為了保存cur的前驅和後繼節點，便於反轉後重新連接。程式碼如下：

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

2. 遞歸方式

遞迴方式雖然不如迭代方式好理解，但其實是一個很好的練習遞迴想法的例子。遞歸操作需要注意的是，在遞歸到鍊錶尾部之後，需要將尾節點賦值給head的Next節點，然後將尾節點傳回為新的head。程式碼如下：

func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

反轉部分鍊錶

有了反轉鍊錶的基礎，我們來看看如何反轉部分鍊錶。題目描述如下：

給定一個鍊錶和兩個整數m和n，反轉從位置m到n的鍊錶。要求給出一種是演算法實作。

透過觀察題目，我們可以將他拆分成三個部分來考慮：

1. m之前: 不需要反轉鍊錶
2. m到n之間: 需要反轉鍊錶
3. n之後: 不需要反轉鍊錶

#因此，我們需要用pre和tail變數來記錄第一部分的尾節點和第二部分的頭節點，然後將第二部分進行反轉操作，反轉後將第一部分的尾節點和第二部分的頭節點連接即可。

程式碼如下：

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m <= 0 || n < m {
        return head
    }
    
    // 特判，如果m=1，则不需要第一部分
    if m == 1 {
        return reverseN(head, n)
    }
    
    //  遍历到m-1位置，记录pre和tail
    var pre *ListNode = nil
    cur := head
    for i := 1; i < m; i++ {
        pre = cur
        cur = cur.Next
    }

    tail := cur // tail 记录第一部分的末尾是 cur             
    // 将第二部分进行反转操作
    new_head := reverseN(cur, n - m + 1)

    // 将第一部分与第二部分重新连接
    tail.Next = new_head
    if pre != nil {
        pre.Next = tail
        return head
    } else {
        return tail
    }
}

// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }
    if n == 1 {
        return head
    }
    var pre *ListNode = nil
    cur := head
    for i := 1; i <= n && cur != nil; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    head.Next = cur
    return pre
}

總結

反轉鍊錶是鍊錶類面試題的常客，掌握這個演算法想法不僅可以解決反轉鍊錶問題，還能擴展到其他鍊錶變換操作。在進行面試時，反轉鍊錶可能用作其他題目的子例，對於開拓思路非常重要。在golang中實作反轉鍊錶和反轉部分鍊錶演算法，需要注意指標的使用、Nil的判斷等問題，熟練後程式碼實作起來非常簡單。

以上是反轉部分鍊錶golang的詳細內容。更多資訊請關注PHP中文網其他相關文章！