链表基础

链表概念的讲解

链表是什么：

链表是一种线性数据结构，每个节点都存有数据，通过指针将各个节点链接在一起。

链表的性质：

• 一致性: 每个节点有相同的数据结构，相同的数据大小，内存中占据相同的大小，存储相同的数据类型。
• 有序性: 节点之间的相对顺序固定，排在某节点前面的节点就是它的前驱，后面的节点就是它的后继，所以定义里面有’线性’。

链表的分类：

链接方式分类：单向链表，双向链表。

ps: 代码展示只用单链表举例。

单链表结构

单链表中的每个结点包含数据+指向后继节点的指针，通过这种方式，单链表将所有结点按顺序组织起来。

节点定义：

class Node(object):   
    """单链表结构的Node节点"""    
    def __init__(self, data, next_node=None):        
        """
        Node节点的初始化方法。        
        data:存储的数据        
        next:下一个Node节点的引用地址       
        """        
        self.data = data        
        self.next = next_node

双链表结构

双链表中的每个节点包含数据+指向前驱和后继的指针。

链表的基本操作：

链表基本操作: 插入、搜索、删除。

以下分别讲每个操作是如何进行的，时间复杂度多少，为什么是那么多，根据时间复杂度判断链表的适合场景。

查找

按照索引/值查找：遍历找到对应的位置/值，然后返回该节点。

# 按照值查找
node = head_node
while node.data != value:    
    node = node.next_node

# 按照索引查找
pos = 0
while pos != index:    
    node = node.next_node    
    pos += 1

时间复杂度：是线性遍历的，所以时间复杂度是 O(n)。因为时间复杂度相对较高，所以在大量数据需要经常用检索的时候就不要用链表了。

插入

按照 index 插入

1. 先创建新节点 new_node；
2. 找到要插入的位置的前驱节点 pre；
3. 新节点 new_node 指向 pre 的后继节点；
4. pre 指向新节点。

new_node.next = pred.next
pred.next = new_node

时间复杂度：由于第2步要线性遍历去找 index 位置，所以时间复杂度是 O(n)。如果插入在头部，就不需要找位置，时间复杂度是 O(1)。

删除

如何做删除的？

1. 找到待删节点的前驱 pred；
2. 把它的前驱节点的后继指向待删节点后继的后继。

pred.next = pred.next.next

时间复杂度：因为要去找前驱，所以线性遍历，时间复杂度是 O(n)。如果删除头部，就不需要找位置，时间复杂度是 O(1)。

链表常见的考点:

哑节点(边界条件)-用于简化边界情况，链表为空或链表的头结点和尾节点。解决办法：自己创建一个哑节点，然后把它的后继连接原节点。

链表的实际应用，通常用于顺序记录的存储，无需提前分配空间，仅适用小规模数据存储。

对于适用的操作属性来说，链表适合查找少，无需排序的使用场景，原因:是链表的查找效率不高，通过调整指针可以快速调节节点的相对位置。

业界应用: 小规模日志记录（通话记录或通讯录），读到内存中后可以以链表的方式进行存储；操作系统中内存快的缓存也可以用链表来实现，LRU 缓存(利用了链表快速调整相对位置优势)。

模式识别

以下这些适用解决链表相关问题。

runner and chaser 类型

题目中有关键词: 要寻找每个特定位置/相对位置。就用后移速度不同的快慢指针来解决使

遍历并处理节点: 处理包括交换，改数值，改指针，删除等等

这类问题的处理方式是每次操作都是当前节点或某类节点，每次处理单个或一对节点；处理的时候，先改变前驱指针，再改变当前节点指针，否则当前节点的 next 信息改变完之后就不对了，通过先改变前驱的指针到达一个保存状态的目的。要动一个元素的后继之前，先保存它的后继。

处理两个或多个链表

处理方式是用 while 循环进行常规处理，循环条件是 list1 非空并且 list2非空，当循环跳出后处理剩下的非空列表。循环至空，再处理剩余。

应用递归处理(涉及链表倒序处理问题)

解决当前问题依赖于存在的相似结构的子问题；利用调用函数本身，先解决子问题，再利用子问题的结果解决当前的问题，递归的出口通常是问题的初始条件 n=1 的情况。链表问题一旦需要倒序处理或与树之间的数据结构进行相互转换往往会用到递归，或者用栈来解决。

给定一个单链表

1. 如何判断链表是否存在环?

2. 如何知道环的长度?

3. 如何找出环的连接点在哪里?

4. 带环链表的长度?

解法:

1. 对于问题1

使用追赶的方法（快慢指针）,设定两个指针show,fast,从头节点开始,每次分别前进1步,2步,如存在环则两者必然会相遇,如不存在环,则fast遇到null退出,并且碰撞点到头节点的距离为环中节点数n.

2. 对于问题2:

记录下问题1的碰撞点p,碰撞点p肯定是在环中的,从这个节点触发,一边移动一边计数再次回到这个节点就得到了环中节点数n

3. 对于问题3:

有定理: 碰撞点p到连接点的距离=头节点到连接点的距离,因此分别从碰撞点,头节点相同速度开始走相遇的那个点就是连接点.
定理证明如下:

设头节点到连接点的距离为x,连接点到碰撞点的距离为y,碰撞点到连接点的距离为z,环的长度为n,
(1) 碰撞点到头节点的距离为n,则有x+y=n
(2) 又因为环的长度为n,则有y+z=n
(3) 由(1),(2) 可得,碰撞点p到连接点的距离=头节点到连接点的距离

4. 对于问题4

问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环链表的长度.

自己实现一个单链表类

实现插入查找删除的功能。

class ListNode(object):
    def __init__(self, value):        
        """        
        value: 节点的数据值        
        next: 节点的后继        
        """        
        self.value = value        
        self.next = None
class MyLinkedList(object):
    def __init__(self):        
        """        
        Initialize your data structure here.        
        """        
        self.head = ListNode(0)
        # 用哑结点来当头节点，方便处理插入和删除的边界情况。        
        self.size = 0
    def get(self, index):        
        """
        按照索引查找        
        Get the value of the index-th node in the linked list. 
        If the index is invalid, return -1.        
        :type index: int        
        :rtype: int        
        """        
        # 异常情况: 如果索引无效 | 索引超出范围        
        if index < 0 or index >= self.size:            
            return -1
        node = self.head
        for _ in range(index + 1): 
        # 记得链表的头结点是哑结点，所以range后界要+1            
        node = node.next
        return node.value # 是返回节点值 
    def addAtHead(self, val):        
        """
        添加到头节点        
        Add a node of value val before the first element of the linked list. 
        After the insertion, the new node will be the first node of the linked list.        
        :type val: int        
        :rtype: None        
        """        
        self.addAtIndex(0, val)

    def addAtTail(self, val):        
        """
        添加到尾节点        
        Append a node of value val to the last element of the linked list.        
        :type val: int        
        :rtype: None        
        """        
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index, val):        
        """
        按照索引添加node        
        :type index: int        
        :type val: int        
        :rtype: None        
        """        
        # 异常情况: 如果索引无效 | 索引超出范围        
        if index < 0 or index >= self.size + 1:            
            return # 什么都不做
        # 找到要加入节点的前驱节点        
        node = self.head
        for _ in range(index):             
            node = node.next
        # 加入新节点        
        new_node = ListNode(val) 
        # 创建新节点        
        new_node.next = node.next        
        node.next = new_node                
        # 链表的总数加1        
        self.size += 1
    def deleteAtIndex(self, index):        
        """
        删除节点        
        因为删除操作的流程是，待删节点node的前驱pre，改变pre后继节点到node的后继节点，所以找的节点应该是pre        
        :type index: int        
        :rtype: None        
        """        
        # 异常情况: 如果索引无效 | 索引超出范围        
        if index < 0 or index >= self.size:            
            return # 什么都不做
        # 找到要删除的节点        
        node = self.head
        for _ in range(index): 
            # 找到待删节点的前驱节点，因为我们已经在头部加了哑结点，所以真正的头部节点是不用单独处理的，按照常规删节点的方式处理            
            node = node.next
        # 删除待删节点        
        node.next =node.next.next        
        # 链表的总数减1        
        self.size -= 1