给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 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
}
}
反转一个单链表。
输入: 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
}
f(n)=f(n-1)+1 其中,f(1)=1
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
}
}
咱们一起来撸下代码,跟着代码流程走一遍。
5->4->3->2->1->NULL
1->2->3->4->NULL
【因为reverseList的作用就是反转】今天我们理解了快慢指针的原理,通过类比的方式我们可以很好的理解并且可以很久的记住它的原理。然后我们分析了递归的实现思路以及递归内部的调用栈。最后我们通过编码实现了链表算法题的解答。在文章最后,我想说的是,递归确实很难理解,如果你真的很想掌握它,那就像我一样,写一个test(intdx:int)函数来测试一下,走一遍递归流程,知道是怎么递的也知道是怎么归的,动手操作了,相信你一定会有惊喜。