在学习编程的路上，底层的原理，乃是必经之路。数据结构与算法正是一道坎，看到了，悟到了，也就学到了。

算法的难度，我觉得不在于学习它。而在于运用，如何将其落地，对简单的落地方式就是使用代码实现出来。在实现的过程，不仅仅是表示，更重要的是明白为什么？

算法题的答案，往往都在20行代码之内，哪怕是一行一行的数，也不需要两分钟，表达出来的思想，值得你我深思。

本文主要讲解数组与链表的内在本质，通过对用的LeetCode的习题实现，进行算法思想的理解。

所有的内容都是提问式表示，因为我觉得大段的文字并不能表达问题的边界，谁知道这个边界自己还在遵循没，还不如来一个直接的方式，以问题为导向，表达最核心的内容。

1.什么是数组？答: 数组是一种线性表数据结构。使用一组连续的内存空间，来存储一组具有相同类型的数据。

注意: 内存指的就是计算的内存，注意必须是连续的。连续表示的是内存是一段，并且必须是相同类型的数据，类型就是编程语言中的基本数据类型。

2.数组的各种操作时间复杂度？描述一下。答: 数组查询时间复杂度是O(1)。--> 归功于连续内存地址，直接计算数据在内存中的位置即可取出对应的数据。数组插入与删除的时间复杂度是O(n)。--> 这更归功于连续内存地址，为了保证地址内存连续，凡是新增与删除，都需要将数组其后的数据向前移动，直至变成连续内存地址。

注意:这个的插入与删除时间复杂度，如果你认为会有插入到最后一位与删除最后一位，不就是不用移动数据了吗？是的，这种情况是存在的。所以说插入与删除的最好情况时间复杂度是O(1)，最差情况是O(n)，平均情况的时候复杂度是O(n)。

3.谈一下容器与数组，并且区分一下两者。

答: 容器(ArrayList)的最大特点就是可以支持动态扩容，当append操作，到数组已经申请的内存用完的时候，会自动申请新的内存地址(一般申请内存地址为当前的1.5倍空间)，将原本的数据拷贝到新的内存空间中。如果数据量很大，就会很耗时。数组(Array)，是不支持动态扩容的，用完了就完了。需要重新申请内存空间。

注意:没有接触过算法的人，对于内存，指针，内存地址等名词会觉得不自然，时间会让你变得自然。一定要记住，这些都是来自于抽象，其实真实的内存并不是简单地说扩容就扩容，只是进行了抽象。(要是不抽象，就没法玩了....)

4.为什么编程语言的数组都是从0开始索引的吗？难道从1开始不好吗？毕竟人类使用的是十进制数。

答: 从0开始估计就是计算机使用的二进制，从0开始的...真实原因可能是这样子的，数组申请的是连续内存空间，所以第一位元素element，在内存中内存地址就是从0开始的，接着索引为1的元素的内存地址开始位置为 0 + 偏移量 (offset) ，索引为2的元素的内存地址的开始位置为 0 + 2 x 偏移量 ......此时，我需要查询array第二位的元素，就直接使用 1 x offset 就可以得到，也就是直接使用 index * offset。这是使用索引从0开始的方式。当做引从1开始的时候，我想看array第二位的元素，此时就需要进行 ( index - 1 ) * offset。这只是一次的索引，当数据量变为n的时候，是不是就不适用了呢？当然，还有这种可能，c 语言的索引就是从0开始的，继承下来了，毕竟Python都是c语言写的，底层的语言都是从0开始，大家也习惯了...

注意:其实编程，写程序，不仅仅是写程序。编程思想，思考问题的角度，逻辑层面都是很重要的。

1.说一下什么是链表？有哪几种链表的形式？对比一下之间的性能。

答:链表使用的是非连续内存地址，通过指针将零散的内存块串联起来。一般常见的链表有单链表、循环链表、双向链表、双向循环链表。双向链表的性能优于单链表，尤其是在进行插入与删除。

2.说一下链表操作的时间复杂度又是多少？

答: 链表的插入与删除时间复杂度是O(1)。---> 插入的时候，只需要将插入元素指向插入位置的后面，将插入位置前的元素指向被插入的额元素即可。顺序别反了。链表的查找时间复杂度是O(n)。---> 在查找的时候，由于不是连续内存，所以只能一个一个指针指向的去遍历，一旦遍历时间复杂度就上去了。

注意: 时间复杂度是算法的核心指标，这也是学习方法之前就应该懂得的。慢慢的多看，多分析就可以很好地分析出来时间复杂度。在单链表与双向链表中，时间复杂度是不一样的，双向链表的插入与删除相比较单链表而言优。可能，这么一说就和前面说的内容混了，但是这才是关键，时间复杂度也是针对于特定的场景下的。

3.你知道缓存是什么吗？给我讲一下LRU(Least Recently Used)缓存淘汰算法是什么？并说一下时间复杂度。

答:缓存主要存在于浏览器端，代理服务器中，服务器内存中，使用缓存可以减轻服务器压力，可以提高数据的读取性能，在架构设计中可以属于高性能范畴。

LRU淘汰算法可以基于单链表。新访问的数据如果已经存在该链表中，就可以直接将该链表从中删除，并移动到链表的开头。如果数据不再该链表中，就将其加入到链表的头部，此时，如果链表的长度已经满了，就需要阐述最后一个链表数据。

LRU缓存淘汰机制的时间复杂度是O(n)。---> 需要遍历一遍链表查看是不是已经存在链表中了。

1.Reverse Linked List网址: https://leetcode-cn.com/problems/reverse-linked-list/

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

答: 1)这是一个链表反转题，观察示例就可以清楚的明白题目的意思，接着开始准备选择变成语言，书写代码了

2)引入链表的head与nil，并且代码越简洁越好。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, prev = head, None  # 变量赋值new操作，同时进行双变量复制，下面还有三变量
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

3)总结，链表反转，理解起来不难，写起来别写反了。一开始就设置当前的节点cur 指向head，前一个节点是prev 是None，也就反转之后的NULL。接着循环走起来，开始遍历整个链表，将当前的节点node设置为下一个元素，即 cur = cur.next。将前一个node设置为cur，也就是下一个时刻的上一个node。将当前节点的下一个节点设置为上一个节点，此时就出现了新的链表了，也就是最终答案的链表。当前节点的下一个node是NULL的时候，循环就结束了，返回prev。

2.Swap Nodes in Pairs网址: https://leetcode.com/problems/swap-nodes-in-pairs/

Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

答: 1)两两交换节点节点题。注意偶数和奇数，偶数就是两两换位置，但是奇数就最后一位不变，前面的偶数位两两交换。

2)代码实现，简洁为主。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        prev, prev.next = self, head
        while prev.next and prev.next.next:
            a = prev.next
            b = a.next
            prev.next, b.next, a.next = b, a, b.next
            prev = a
        return self.next

3)总结，两两交换需要考虑前一个node与后一个node，中间使用 a 与 b进行切换链表的连接，进而将链表两两交换。这个还是比较绕的，自己画图看看吧!

3.Linked List Cycle网址: https://leetcode-cn.com/problems/linked-list-cycle/

Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:Can you solve it using O(1) (i.e. constant) memory?

答: 1)给你一个链表，让你判断这个链表是不是存在循环链表。是链表内部循环起来了，转圈圈了。

2)方式一:直接暴力破解，定0.5s的时间，就一直进行next去看是不是变成null了，如果变成null，代表这个链表是单链表，否则就是cycle.

import time

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        flag = time.time()
        while head.next:
            head = head.next
            
            if time.time() - flag == 3:
                return True
        return False

3)方式二，使用一个集合将每一次取出的next的内存地址存起来，只要下一个node在集合中，就是有cycle。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        node = set()
        while head.next:
            node.add(id(head.next))
            head = head.next
            if head in node:
                return True            
        return False

4)方式三，使用快慢指针，快指针一次跑两个，慢指针一次跑一个，当快慢指针相等的时候，也就是出现cycle了。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

5)总结，算法的思想不难，重点在于代码实现。需要花费大量的时间。且行且艰辛。

本文从数组与链表的基础讲起，到 LeetCode 做习题，不仅仅是学习两个数据结构，做两道题，而是以后遇到就不在惧怕的过程。

做算法题，确实烧脑，这不是一般的烧脑。希望自己一个月之内刷个三五百道题，祝我好运!

突然有一天，我发现我变强了，我也秃了.....