反转部分链表golang
时间：2023-05-11 18:26
反转链表是一个经典的问题，应用广泛，时间复杂度不高，实现起来也不难。本篇文章将介绍如何在golang中实现一个反转部分链表的算法。 反转链表 先来看看如何反转链表，我们可以用迭代或递归两种方式进行实现。 我们用三个指针pre、cur、next来迭代地进行反转操作，其中pre和next是为了保存cur的前驱和后继节点，便于反转后重新连接。代码如下： 递归方式虽然不如迭代方式好理解，但实际上是一个很好的练习递归思想的例子。递归操作需要注意的是，在递归到链表尾部之后，需要将尾节点赋值给head的Next节点，然后将尾节点作为新的head返回。代码如下： 反转部分链表 有了反转链表的基础，我们来看一下如何反转部分链表。题目描述如下： 给定一个链表和两个整数m和n，反转从位置m到n的链表。要求给出一种是算法实现。 通过观察题目，我们可以将他拆分成三个部分进行考虑： 因此，我们需要用pre和tail变量来记录第一部分的尾节点和第二部分的头节点，然后将第二部分进行反转操作，反转后将第一部分的尾节点和第二部分的头节点连接即可。 代码如下： 总结 反转链表是链表类面试题的常客，掌握这一算法思想不仅可以解决反转链表问题，还能扩展到其他链表变换操作。在进行面试时，反转链表可能用作其他题目的子例，对于开拓思路非常重要。在golang中实现反转链表和反转部分链表算法，需要注意指针的使用、Nil的判断等问题，熟练掌握后代码实现起来非常简单。 以上就是反转部分链表golang的详细内容，更多请关注Gxl网其它相关文章！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}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}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}
