反转部分链表golang-Golang-PHP中文网

反转部分链表golang

WBOY

发布： 2023-05-11 11:34:07

原创

346人浏览过

反转链表是一个经典的问题，应用广泛，时间复杂度不高，实现起来也不难。本篇文章将介绍如何在golang中实现一个反转部分链表的算法。

反转链表

先来看看如何反转链表，我们可以用迭代或递归两种方式进行实现。

迭代方式

我们用三个指针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
}

登录后复制

递归方式

递归方式虽然不如迭代方式好理解，但实际上是一个很好的练习递归思想的例子。递归操作需要注意的是，在递归到链表尾部之后，需要将尾节点赋值给head的Next节点，然后将尾节点作为新的head返回。代码如下：

立即学习“go语言免费学习笔记（深入）”；

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
}

登录后复制

反转部分链表

有了反转链表的基础，我们来看一下如何反转部分链表。题目描述如下：

爱图表

AI驱动的智能化图表创作平台

查看详情

给定一个链表和两个整数m和n，反转从位置m到n的链表。要求给出一种是算法实现。

通过观察题目，我们可以将他拆分成三个部分进行考虑：

m之前: 不需要反转链表
m到n之间: 需要反转链表
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中文网其它相关文章！