---

6-1 链表

---

目录

小节	位置
6.1.1	单链表
6.1.2	双链表
6.1.3	循环链表
6.1.4	链表逆序
6.1.5	顺序表和链表的对比

6.1.1 单链表

链表，别名链式存储结构或单链表，是链式存储结构中最简单和最基本的结构，与顺序表不同，链表不限制数据的物理存储状态。换句话说，使用链表存储的数据元素，其物理存储位置是随机的。在存储每个元素的同时，需要存储其直接后继(或直接前驱）的位置，这一部分称为：链。

6.1.1.1 单链表结点

单向链表的每个元素都由两部分组成，存储元素的 数据域 data，和存储直接后继元素地址的 指针域 next，这样的一种结构成为结点。在C/C++中，可以用 struct 结构体来实现这个结构，在python中我们可以用class类来实现这种结构：

# node
class LNode(object):
    def __init__(self, val=None):
        self.val=val
        self.next=None

6.1.1.2 单链表的实现

单链表在实现时，又可以分为两种情况：不带头结点的单链表、带头结点的单链表，二者的区别可以从下图中看到：

• 这里所谓的“头结点”，就是指的专门设立一个结点node（上面的第2幅图），它的指针域保存的（指向的）是第一个实际存储了元素的区域的地址，如果没有元素，就是NULL。 即不管有没有元素，都有这么一个结点存在。头结点的数据域可以不存储任何信息（也可以存储像线性表的表长那样的数据信息，但一般都不存数据）。通常这个结点也被称为：哑结点。
• 头结点的作用是使所有链表（包括空表）的头指针非空，把空表和非空表的处理统一起来了，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。
• 比如说如果要删除第一个元素，没有头结点的链表，第一个元素的位置就是h，删除第一个元素之后，h 指针就得更新为原来的第二个元素的位置；但是对于有头结点的单链表，由于 h 指针指向的是头结点，所以删除第一个位置的元素和删除其他位置的元素的操作都是一样的，不需要再更新 h 指针！

下面给出不带头结点的链表的python实现方式，因为这种情况处理更难一点，弄懂了这种情况的 code 写法，再写带头结点的链表的实现，就会简单很多。而且在很多场景，其实并没有这么严格的抠字眼说链表带不带头结点，题目中出现的大多数是这里谈及的 “不带头结点” 的单链表，但是也习惯称呼第一个结点为 “头结点”，这并不影响做题 。所以这里只是做一个概念上的了解，知道单链表有这么两种写法即可。在做题时根据实际情况写就行了。

主要涉及到的，就是链表的增、删、改、查操作。

# node
class Node(object):
    def __init__(self, val=None):
        self.val=val
        self.next=None

class Single_Link_List(object):
    def __init__(self, node=None):
        """
        该实现是构造“不带头结点的单链表”
        一定要牢记,head就是第一个元素结点,而非head.next.
        实际上head.next其实已经是第二个元素结点了
        所以下面的某一些操作才会先判断head本身是不是空,即判断链表是否为空，
        """
        self.__head = node

    def get_random_init(self, n=0):
        for k in range(n):
            self.append(random.randint(0, 20))

    def is_empty(self) -> bool:
        return self.__head is None

    def size(self) -> int:
        cnt, cur = 0, self.__head
        while cur is not None:
            cnt += 1
            cur = cur.next
        return cnt

    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.val, end='->')
            cur = cur.next
        print('None')

    ###############【增】###############

    def add(self, val) -> bool:
        '''头插法'''
        node = Node(val)
        node.next = self.__head
        self.__head = node
        return True

    def append(self, val) -> bool:
        '''尾插法'''
        node, cur = Node(val), self.__head
        # 这里就需要先判断是否为空,否则None.next会报错
        if cur is None:
            self.__head = node
            return True
        else:
            # 循环结束后，cur指向最后一个数据结点
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            return True

    def insert(self, pos, val) -> bool:
        '''随机位置插入'''
        # 先确保传入的pos属于[0, size]
        if pos < 0 or pos > self.size():
            print("insert pos out of range!")
            return False
        else:
            if pos == 0:
                return self.add(val)
            else:
                node = Node(val)
                i, cur = 0, self.__head
                # 循环结束后, cur指向pos-1的位置，因为pos的位置要留给node
                while cur.next is not None and i < pos-1:
                    cur = cur.next
                    i += 1
                    # print('i:',i,end='->')
                    # print(cur.val)
                node.next = cur.next
                cur.next = node
                return True

    ############### 【删】###############
    def remove(self, val) -> bool:
        '''根据值来删除第一个符合条件的结点'''
        if self.is_empty():
            print("the linklist is empty!")
            return False

        pre, cur = None, self.__head
        while cur is not None:
            if cur.val == val:
                # 先要判断是否删除的是首结点
                if cur == self.__head:
                    # 更新首结点
                    self.__head = self.__head.next
                    cur = self.__head
                    return True
                else:
                    pre.next = cur.next
                    cur = pre.next
                    return True
            else:
                pre = cur
                cur = cur.next
        return False

    def del_pos(self, pos) -> bool:
        '''根据位置来指定删除'''
        if pos < 0 or pos > self.size()-1:
            print("del pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            # 先要判断是否删除的是首结点
            if pos == 0:
                # 更新首结点
                self.__head = self.__head.next
                return True
            else:
                i = 0
                pre, cur = None, self.__head
                # 循环结束后, cur指向pos的位置
                while cur.next is not None and i < pos:
                    pre = cur
                    cur = cur.next
                    i += 1
                pre.next = cur.next
                return True

    ############### 【改】###############
    def change(self, pos: int, val) -> bool:
        '''根据位置改变值'''
        if pos < 0 or pos > self.size()-1:
            print("change pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            cur.val = val
            return True

    ############### 【查】###############
    def find(self, val):
        '''依据值来定位位置(索引)'''
        i, cur = 0, self.__head
        while cur is not None:
            if cur.val == val:
                return i
            else:
                i += 1
                cur = cur.next
        print('not find %s' % str(val))
        return False

    def locate(self, pos: int):
        '''依据索引查找值'''
        if pos < 0 or pos > self.size()-1:
            print("out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            return cur.val 

6.1.1.3 带头结点单链表的实现

带头结点的单链表逻辑思考上更为简单一点，其与【不带头结点】的链表的核心差别主要有以下：

1. head 一定不为空，在首结点进行操作时，与其他位置的操作是一致的；
2. 当游标cur 指向 head 时，其索引为 -1，表示首结点的前一位置，即首结点是从 head.next 开始算起。

掌握好这两个关键点，实现起来就十分简单了.

class Single_Link_List_With_Head(object):
    def __init__(self, node=None):
        """
        这里实现的是所谓【带头结点】的单链表
        所以初始化时不是为None或者从外面传入的node
        初始化时就一定是一个结点，我们可以用这个结点的数据域来存储链表的长度
        """
        self.__head = Node(0)
        self.__head.next = node
    
    def is_empty(self)->bool:
        return self.__head.next is None
    
    def size(self)->int:
        cnt, cur = 0, self.__head
        while cur.next is not None:
            cnt +=1
            cur = cur.next
        # self.__head.val = cnt  # 也可以用头结点的数据域来存储链表长度    
        return cnt
    
    def travel(self):
        cur = self.__head
        while cur.next is not None:
            cur = cur.next
            print(cur.val, end='->')
        print('None')
            
    ###############【增】###############
    def add(self, val)->bool:
        node = Node(val)
        # 注意这一步和不带头结点的链表的区别
        node.next = self.__head.next
        self.__head.next = node
        return True
    
    def append(self, val)->bool:
        node= Node(val)
        cur = self.__head
        # 这里就不用单独判断链表是否为空了
        # 空链表也包含在下面的情况
        while cur.next is not None:
            cur = cur.next
        cur.next = node
        return True
    
    def insert(self, pos:int, val)->bool:
        if pos < 0 or pos > self.size():
            print('failed! insert pos out of range!')
            if self.__head.next is None:
                print('empty link-list!')
            return False
        
        else:
            node = Node(val)
            i, cur = -1, self.__head
            while cur.next is not None and i<pos-1:
                cur = cur.next
                i+=1
            node.next = cur.next
            cur.next = node
            return True
    
    ###############【删】###############
    def remove(self, val)->bool:
        if self.is_empty():
            print('empty link-list!')
            return False
        
        pre, cur = self.__head, self.__head.next
        while cur is not None:
            if cur.val == val:
                pre.next = cur.next
                return True
            else:
                pre = cur
                cur = cur.next
        print('not find %s' % str(val))
        return False
    
    def del_pos(self, pos:int)->bool:
        """
        删除指定pos的结点
        与【不带头结点】的单链表对比,不用特殊处理首结点(pos==0)的删除
        只是索引从-1开始,其他的部分不变
        """
        if pos < 0 or pos > self.size()-1:
            print('failed! insert pos out of range!')
            if self.__head.next is None:
                print('empty link-list!')
            return False
        
        else:
            i, cur = -1, self.__head
            while cur.next is not None and i < pos-1:
                cur = cur.next
                i+=1
            
            cur.next = cur.next.next
            return True

    ############### 【改】###############
    def change(self, pos: int, val) -> bool:
        '''根据位置改变值'''
        if pos < 0 or pos > self.size()-1:
            print("change pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = -1, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            cur.val = val
            return True

    ############### 【查】###############
    def find(self, val):
        '''依据值来定位位置(索引)'''
        i, cur = -1, self.__head
        while cur.next is not None:
            cur = cur.next
            i += 1
            if cur.val == val:
                return i             
                
        print('not find %s' % str(val))
        return False

    def locate(self, pos: int):
        '''依据索引查找值'''
        if pos < 0 or pos > self.size()-1:
            print("out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = -1, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            return cur.val

6.1.2 双链表

双向链表除了相当于在单链表的基础上，每个结点多了一个指针域prior，用于存储其直接前驱的地址。同时保留有next，用于存储其直接后继的地址。

所以对于双链表，其实很多操作都和单链表是一样的，因为你完全可以忽视掉它有个 prior指针，这样就可以当做单链表来使用。

因为有了prior指针，所以在插入和删除新元素时，应该考虑可以利用这一值。
鉴于有些操作其实可以和单链表保持一致，比如判空、求长度、遍历、查找等等，所以我们可以用类的继承来实现双链表，主要要修改的其实就是增、删元素两种操作，因为涉及到“链”的变化。
特别注意：在更新某结点node的prior链接时，也要记得check一下该node是否为空！
下面的code是继承不带头结点的单链表的类来进行实现。

class D_Node(object):
    def __init__(self, val=None):
        self.val = val      # 数据源
        self.next = None    # 后继
        self.prior=None     # 前驱

class Double_Link_List(object):
    def __init__(self, node=None):
        self.__head = node
    
    def get_random_init(self, n=0):
        for k in range(n):
            self.append(random.randint(0, 20))
    
    '''普通的三项基本操作和简单的单链表一样'''
    def is_empty(self):
        return self.__head is None

    def size(self) -> int:
        cnt, cur = 0, self.__head
        while cur is not None:
            cnt += 1
            cur = cur.next
        return cnt 

    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.val, end='->')
            cur = cur.next
        print('None')

    ###############【增】###############
    '''增加元素的操作一定要记得 prior 指针连接上'''
    def add(self, val) -> bool:
        '''头插法'''
        node = D_Node(val)
        node.next = self.__head
        if self.__head is not None:
            self.__head.prior = node
        self.__head = node
        return True

    def append(self, val) -> bool:
        '''尾插法'''
        node, cur = D_Node(val), self.__head
        # 这里就需要先判断是否为空,否则None.next会报错
        if cur is None:
            self.__head = node
            return True
        else:
            # 循环结束后，cur指向最后一个数据结点
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prior = cur
            return True
    
    def insert(self, pos, val) -> bool:
        '''随机位置插入'''
        # 先确保传入的pos属于[0, size]
        if pos < 0 or pos > self.size():
            print("insert pos out of range!")
            return False
        else:
            if pos == 0:
                return self.add(val)
            else:
                node = D_Node(val)
                i, cur = 0, self.__head
                # 循环结束后, cur指向pos-1的位置，因为pos的位置要留给node
                while cur.next is not None and i < pos-1:
                    cur = cur.next
                    i += 1
                    # print('i:',i,end='->')
                    # print(cur.val)
                node.next = cur.next
                cur.next = node
                
                node.prior = cur
                if node.next is not None:
                    node.next.prior = node
                return True

    ############### 【删】###############
    '''删除元素的操作也要记得重置prior'''
    def remove(self, val) -> bool:
        '''根据值来删除第一个符合条件的结点'''
        if self.is_empty():
            print("the linklist is empty!")
            return False

        pre, cur = None, self.__head
        # 这里的 pre 完全可以用 cur.prior 来表示，我懒得改了
        while cur is not None:
            if cur.val == val:
                # 先要判断是否删除的是首结点
                if cur == self.__head:
                    # 更新首结点
                    self.__head = self.__head.next
                    # 判断更新后的 self.__head 是否为空
                    if self.__head is not None:
                        self.__head.prior = cur.prior
                    cur = self.__head
                    return True
                else:
                    pre.next = cur.next
                    # 判断 cur.next 是否为空
                    if cur.next is not None:
                        cur.next.prior = pre
                    cur = pre.next
                    return True
            else:
                pre = cur
                cur = cur.next
        return False

    def del_pos(self, pos) -> bool:
        '''根据位置来指定删除'''
        if pos < 0 or pos > self.size()-1:
            print("del pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            # 先要判断是否删除的是首结点
            if pos == 0:
                # 更新首结点
                self.__head = self.__head.next
                # 判断更新后的 self.__head 是否为空
                if self.__head is not None:
                    self.__head.prior = None
                return True
            else:
                i = 0
                # 这里的 pre 完全可以用 cur.prior 来表示，我懒得改了
                pre, cur = None, self.__head
                # 循环结束后, cur指向pos的位置
                while cur.next is not None and i < pos:
                    pre = cur
                    cur = cur.next
                    i += 1
                pre.next = cur.next
                if cur.next is not None:
                    cur.next.prior = pre
                return True


    ############### 【改】###############
    '''改元素值不涉及重连，所以与单链表一样'''
    def change(self, pos: int, val) -> bool:
        '''根据位置改变值'''
        if pos < 0 or pos > self.size()-1:
            print("change pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            cur.val = val
            return True

    ############### 【查】###############
    '''改元素值不涉及重连，所以与单链表一样'''
    def find(self, val):
        '''依据值来定位位置(索引)'''
        i, cur = 0, self.__head
        while cur is not None:
            if cur.val == val:
                return i
            else:
                i += 1
                cur = cur.next
        print('not find %s' % str(val))
        return False

    def locate(self, pos: int):
        '''依据索引查找值'''
        if pos < 0 or pos > self.size()-1:
            print("out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next is not None and i < pos:
                i += 1
                cur = cur.next
            return cur.val

6.1.3 循环链表

循环链表就是链表首尾相接连成一个环，即链表的最后一个结点，的后继结点，是头（首）结点；可以用单向链表和双向链表来实现，分别形成单向循环链表和双向循环链表，又可再分为带头结点和不带头结点，这里只画出不带头结点的单向循环链表的例子示意图如下：

所以判断是否是最后一个元素 的条件 也从 p->next != null; 变成了 p->next != head;

class Single_Cycle_Link_list(object):
    """单向循环链表"""
    def __init__(self):
        self.__head = None

    def get_random_init(self, n=0):
        for k in range(n):
            self.append(random.randint(0, 10))

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head is None
    
    def size(self)->int:
        if self.is_empty():
            return 0
            
        cnt, cur = 1, self.__head
        while cur.next != self.__head:
            cur = cur.next
            cnt +=1
        return cnt 

    def travel(self):
        if self.is_empty():
            print('None')
        
        cur = self.__head
        print(cur.val, end='->')

        while cur.next != self.__head:
            cur = cur.next
            print(cur.val, end='->')
        print('None')
    
    ###############【增】###############
    def add(self, val):
        node = Node(val)
        if self.is_empty():
            self.__head = node
            # 循环链表要记得尾部也指向head
            node.next = self.__head
            return True
        
        else:
            node.next = self.__head
            cur = self.__head
            # 循环结束后，cur到链表尾部
            while cur.next != self.__head:
                cur = cur.next
            
            # 将尾部的next指向node, 并将node更新为新的head
            cur.next = node
            self.__head = node
            return True

    def append(self, val) -> bool:
        '''尾插法'''
        node, cur = Node(val), self.__head
        # 这里就需要先判断是否为空,否则None.next会报错
        if cur is None:
            self.__head = node
            # 循环链表要记得尾部也指向head
            node.next = self.__head
            return True
        else:
            # 循环结束后，cur指向最后一个数据结点
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            # 将node后继指向 head
            node.next = self.__head
            return True
    
    def insert(self, pos, val) -> bool:
        '''随机位置插入'''
        # 先确保传入的pos属于[0, size]
        if pos < 0 or pos > self.size():
            print("insert pos out of range!")
            return False
        else:
            if pos == 0:
                return self.add(val)
            else:
                node = Node(val)
                i, cur = 0, self.__head
                # 循环结束后, cur指向pos-1的位置，因为pos的位置要留给node
                while cur.next != self.__head and i < pos-1:
                    cur = cur.next
                    i += 1
                    # print('i:',i,end='->')
                    # print(cur.val)
                node.next = cur.next
                cur.next = node
                return True

    ############### 【删】###############
    def remove(self, val) -> bool:
        '''根据值来删除第一个符合条件的结点'''
        if self.is_empty():
            print("the linklist is empty!")
            return False

        cur = self.__head
        # 先要判断首结点的值是否符合删除条件
        if cur.val == val:
            # 如果链表只有一个结点
            if cur.next == self.__head:
                self.__head = None
                return True
            else:
                # 循环结束后cur指向最后一个结点
                while cur.next != self.__head:
                    cur = cur.next 
                # 将尾部与新的首结点连起来
                cur.next = self.__head.next
                self.__head = self.__head.next
                return True

        else: # 说明首结点的值不符合
            pre, cur = self.__head, self.__head.next
            while cur != self.__head:
                if cur.val == val:
                    pre.next = cur.next 
                    return True
                else:
                    pre = cur
                    cur = cur.next
            
        print('not find %s ' % str(val))
        return False

    def del_pos(self, pos) -> bool:
        '''根据位置来指定删除'''
        if pos < 0 or pos > self.size()-1:
            print("del pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            # 先要判断是否删除的是首结点
            if pos == 0:
                cur = self.__head
                # 如果链表只有一个结点
                if cur.next == self.__head:
                    self.__head = None
                    return True
                else:
                    # 循环结束后cur指向最后一个结点
                    while cur.next != self.__head:
                        cur = cur.next 
                    #print('end val:', cur.val)
                    # 将尾部与新的首结点连起来
                    cur.next = self.__head.next
                    self.__head = self.__head.next
                    return True

            else:
                i = 1
                pre, cur = self.__head, self.__head.next
                # 循环结束后, cur指向pos的位置
                while cur != self.__head and i < pos:
                    pre = cur
                    cur = cur.next
                    i += 1
                pre.next = cur.next
                return True

    ############### 【改】###############
    def change(self, pos: int, val) -> bool:
        '''根据位置改变值'''
        if pos < 0 or pos > self.size()-1:
            print("change pos out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next != self.__head and i < pos:
                i += 1
                cur = cur.next
            cur.val = val
            return True

    ############### 【查】###############
    def find(self, val):
        '''依据值来定位位置(索引)'''
        if self.is_empty():
            print('the linklist is empty!')
            return False
        
        if self.__head.val == val:
            return 0
        else:
            i, cur = 1, self.__head.next
            while cur != self.__head:
                if cur.val == val:
                    return i
                else:
                    i += 1
                    cur = cur.next
        
        print('not find %s' % str(val))
        return False

    def locate(self, pos: int):
        '''依据索引查找值'''
        if pos < 0 or pos > self.size()-1:
            print("out of range!")
            if self.is_empty():
                print('the linklist is empty!')
            return False
        else:
            i, cur = 0, self.__head
            # 循环结束后, cur指向pos的位置
            while cur.next != self.__head and i < pos:
                i += 1
                cur = cur.next
            return cur.val

6.1.4 链表逆序

链表逆序就是把一个链表的尾变头，头变尾。属于链表中的经典问题。

6.1.4.1 方案一

将第二个结点后面的元素依次插入到第一个结点后面，
这个方法对于带不带头结点的链表都适用。
举例
① 不带头结点的链表
原始链表，其中第二个元素是 B
A -> B-> ==C== -> D -> E -> F -> null
先进入循环,不断的把B的后继元素往第一个元素后面插
A -> C -> B -> ==D== -> E -> F -> null #将上面 B后的 C 插入到A后面
A -> D -> C -> B -> ==E== -> F -> null #将上面 B后的 D 插入到A后面
A -> E -> D -> C -> B -> ==F== -> null #将上面 B后的 E 插入到A后面
A -> F -> E -> D -> C -> B -> null #将上面 B后的 F 插入到A后面
最后将F作为新的首结点,将A放到B后面：
F -> E -> D -> C -> B -> A -> null

def reverse(self) -> bool:
    if self.is_empty():
        print('empty link-list!')
        return False
    elif self.__head.next is None:
        return True
    else:
        node_A, node_B = self.__head, self.__head.next
        while node_B.next is not None:
            # 相当于先把B后的结点从链表中断开
            node_C = node_B.next
            node_B.next = node_C.next
            # 然后插入首结点后面
            node_C.next = node_A.next
            node_A.next = node_C

        # 尾首相连，相当于形成了一个循环链表了
        node_B.next = node_A
        # 然后从A点next处断开即可
        self.__head = node_A.next
        node_A.next = None
        return True

② 带头结点的链表
可以将头结点视为第一个元素，那么就是直接把 A 的后继元素不断的往head后面插：
带头结点原始链表，将头结点视为第1个元素，那么其中第2个元素是 A
Head -> A -> ==B==-> C -> D -> E -> F -> null
先进入循环,不断的把A的后继元素往头结点后面插
Head -> B -> A -> ==C== -> D -> E -> F -> null
Head -> C -> B -> A -> ==D== -> E -> F -> null
Head -> D -> C -> B -> A -> ==E== -> F -> null
Head -> E -> D -> C -> B -> A -> ==F== -> null
Head -> F -> E -> D -> C -> B -> A -> null

def reverse(self) -> bool:
    if self.is_empty():
        print('empty link-list!')
        return False
    elif self.__head.next.next is None:
        return True
    else:
        node_H, node_B = self.__head, self.__head.next
        while node_B.next is not None:
            # 相当于先把B后的结点从链表中断开
            node_C = node_B.next
            node_B.next = node_C.next
            # 然后插入头结点后面
            node_C.next = node_H.next
            node_H.next = node_C

        # 循环结束之后，结点B后的结点都被逆序插入到A之后
        # 由于A是作为头结点head一直稳定不变，所以已经结束了
        return True

6.1.4.2 方案二

直接利用辅助变量，将node一个一个改变指向，这个方法就是要注意中间一定不能断了。

def reverse(self, head):
    pre, cur = None, head
    while cur:
        # 先保存剩余部分的头
        rest = cur.next
        # 当前结点指向前面
        cur.next = pre
        # pre指针移动到当前结点
        pre = cur
        # cur指针指向剩下部分的头
        cur = rest
    return pre

6.1.4.3 方案三

采用递归的思路

① 不带头结点
递归其实就是一直要找到最后一个结点，然后每次改一下。
这个时候其实 函数递归的时，函数用系统栈存储了前面每个结点的信息，所以一步一步从最后面改动到前面去，最后返回了一个以原始尾结点的地址为头指针的 无头结点单链表。

def reverse_linklist_by_recursion(self):
    # 调用递归函数, 更新新的首结点
    self.__head = self.__recursion_func(self.__head)
    return True

def __recursion_func(self, node):
    # 结束的条件:链表为空或者链表最后一个节点
    if node is None or node.next is None:
        return node
    # 递归调用
    node_new = self.__recursion_func(node.next)

    # 每次都把当前结点 重新设置成 当前结点的下一个结点的下一个结点
    node.next.next = node
    # 然后再把当前结点的新后继设置为空，相当于当前结点作为新链表的尾结点
    node.next = None

    return node_new

② 带头结点
其实依然可以用上面的函数，只是不能把头结点传入进去，因为头结点本身不该算在链表的存储的数据中。我们可以把带头结点的单链表的头结点后面的那部分，看成是不带头结点的单链表，即可复用上面的函数了。即，传入的指针应该是 head->next

def __reverse_linklist_by_recursion(self):
    # 这里直接把self.__head.next之后的链表，当作不带头结点的链表处理即可
    self.__head.next = self.recursion_func(self.__head.next)
    return True

def __recursion_func(self, node):
    # 结束的条件:链表为空或者链表最后一个节点
    if node is None or node.next is None:
        return node
    # 递归调用
    node_new = self.__recursion_func(node.next)

    # 每次都把当前结点 重新设置成 当前结点的下一个结点的下一个结点
    node.next.next = node
    # 然后再把当前结点的新后继设置为空，相当于当前结点作为新链表的尾结点
    node.next = None

    return node_new

6.1.5 顺序表和链表的对比

• 存储结构的不同
  虽然它们同属于线性表，但数据的存储结构有本质的不同：
  顺序表存储数据，需预先申请一整块足够大的存储空间，然后将数据按照次序逐一存储，逻辑关系就是靠元素间物理空间上的邻接关系来维持
  链表 ，什么时候存储数据，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持，
• 空间利用率
  顺序表的空间利用率显然要比链表高。
  首先是链表每个结点不光有数据域，还有指针域。这就比顺序表多耗费一点空间。
  链表在存储数据时，每次只新开辟一个node的空间，且位置是随机的，会产生很多空间碎片，一定程序上造成了空间浪费。
• 时间复杂度
  根据顺序表和链表在存储结构上的差异，问题类型主要分为以下 2 类：
  第 1 类问题：主要涉及访问元素的操作，元素的插入、删除和移动操作极少；
  适合使用顺序表。这是因为，顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度为 O(1)；如果要在链表中访问元素，需要从头指针依次遍历，直到找到指定节点，花费的时间复杂度为 O(n).
  第 2 类问题:主要涉及元素的插入、删除和移动，访问元素的需求很少；
  适合使用链表。链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，不用大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，时间复杂度至少为 O(n).