最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

leetcode 递归编程技巧-链表算法题

XAMPP新闻 admin 289浏览 0评论

开篇问题1:leetcode 141:环形链表

题目描述:

给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。否则,返回 false 。

示例:

zzzzzs0000073

解题思路:

实用快慢指针的思想。
类比:就比如学校操场,A、B两人跑围着操场跑步,A跑的慢,B跑的快,他们从开始起跑后,随着时间的推移,最终他们会在操场的某个地点相遇。
如果A、B在一个高速公路上跑,一个慢一个快,他们始终都没有机会相遇。
快慢指针就是使用上述的原理,slow指针一次走一步,quick指针一次走两步。通过这样的方式遍历整个链表。如果没相遇就说明没有环,就像高速公路。如果彼此相遇了,说明有环,就像学校操场上的环形跑道。

 

编码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution: NSObject {
    func hasCycle(_ head: ListNode?) -> Bool {
        if head == nil || head?.next == nil { return false }
        var slow = head
        var fast = head?.next
        while fast != nil && fast?.next != nil {
            if slow === fast { return true }
            slow = slow?.next
            fast = fast?.next?.next
        }
        return false
    }
}

问题2:leetcode 141:反转链表

题目描述:

反转一个单链表。

示例:

输入: 5->4->3->2->1->NULL
输出: 1->2->3->4->5->NULL

递归:

先举一个例子:【非原创】
周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”。基本上,所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子”,我们用递推公式将它表示出来就是这样的:

f(n)=f(n-1)+1 其中,f(1)=1

f(n) 表示你想知道自己在哪一排,f(n-1) 表示前面一排所在的排数,f(1)=1 表示第一排的人知道自己在第一排。有了这个递推公式,我们就可以很轻松地将它改为递归代码,如下:

int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

通过上述的例子,大家对递归应该有一个比较清楚的认识了。那么在实际开发中,递归中的代码是怎么运行的了,我们来看下面的代码:

   func test(index: Int) -> Int{
        if index == 0 { return 0}
        print("-------\(index)") //第一行打印,记为A
        let result = test(index: index-1)
        print("=======\(index)") //第一行打印,记B
        return result
    }
text(index:2)

【问题:里面的A和B打印顺序是怎么样的?】

打印结果:
-------2
-------1
=======1
=======2

怎么理解了? 我把代码改写成这样你就理解了

    func test(index: 2){
        print(-------2)
        let result = {
            func test(1){
                print(-------1)
                let result = test(0)
                print(=====0)
            }
        }
        print(======2)
        return result
    }

递归思路

  1. 电影院例子中的方法f就是用来求当前位置处于哪一排 –>知道方法f的作用
  2. 实现的公式是f(n)=f(n-1)+1 其中,f(1)=1
  3. 放手让它自己运行吧

解答问题2

1.reverseList函数是用来反转链表的
2.实现公式:

newHead = reverseList(head.next)
head.next.next = head
head = nil

3.递归下去

编码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
  func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil { return head }
        let newHead = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return newHead
    }
}

如何简单正确的理解了?

咱们一起来撸下代码,跟着代码流程走一遍。

  1. 我们输入5->4->3->2->1->NULL
  2. head=5 不为空,然后执行reverseList(head?.next)即reverseList(4)
  3. 到了第2步,reverseList(4)的最后的得到的结果是1->2->3->4->NULL【因为reverseList的作用就是反转】
  4. head.next.next = head即head.next.next = 5
  5. 最后head=nil
  6. done
    需要把reverseList(head)当作一个整体。事实上,程序也是这样运行的。

总结

今天我们理解了快慢指针的原理,通过类比的方式我们可以很好的理解并且可以很久的记住它的原理。然后我们分析了递归的实现思路以及递归内部的调用栈。最后我们通过编码实现了链表算法题的解答。在文章最后,我想说的是,递归确实很难理解,如果你真的很想掌握它,那就像我一样,写一个test(intdx:int)函数来测试一下,走一遍递归流程,知道是怎么递的也知道是怎么归的,动手操作了,相信你一定会有惊喜。

转载请注明:XAMPP中文组官网 » leetcode 递归编程技巧-链表算法题

您必须 登录 才能发表评论!