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

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

题目描述：

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

示例：

解题思路：

实用快慢指针的思想。
类比：就比如学校操场，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 递归编程技巧-链表算法题