三、链表（Linked list）以及LeetCode题

一、概述

1.1、为什么我们要引入链表
首先，顺序表的构建是预先知道数据的大小来申请连续的存储空间，在进行扩充的时候，是需要进行数据的迁移的，这样就使得顺序表用起来不是那么的灵活。链表结构就充分利用到了计算机的内存空间，实现了灵活的内存动态管理。
1.2、链表的定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
下图是一个简单的链表的示意图：

二、单向链表

也就是我们说的单链表，属于最简单的一种形式。根据前面内容，我们知道链表的节点中含有数据区和连接区：

• 数据区用来存放具体数据
• 连接区就是用来指向下一个节点的内存地址的。这里需要注意最后的一个节点（尾节点）的连接区是指向的一个空值的。
• 变量p指向的是链表的头节点。那么从p节点开始就能找到表中的任意节点。

单链表节点与单链表示意图

现在我们知道单链表的结构了，那么下面我们如何来实现这样的数据结构呢？
用类的形式来实现这个数据结构与算法。我们产生一个数据结构的时候，要把关于这个数据结构以及它所支持的操作放到一起，形成一个整体，这个时候就是面向对象一个类的思想了，所以对于实现数据结构，我们得思考：1、需要解决数据结构的保存问题，2、定义这样的数据结构要支持什么样的操作。
节点实现

class SingleNode(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None

单链表的操作

操作	解释
is_empty()	判断链表是不是空的
length()	得到链表的长度
travel()	对链表进行遍历
add(item)	给链表的头部增加元素item
append(item)	在链表的尾部增加元素item
insert(pos, item)	在指定的位置pos插入元素item
remove(item)	删除元素item
search(item)	查找节点是否存在

我们先写出一个节点类，那么这个类每实例化出一个对象，那么这个对象就应该有数据区(elem)和链接区(next)。这样可以生产出node1、node2这样的节点，但是这个时候node1和node2还没有什么关联。让node1的连接区指向node2，那么它们就相互关联了起来。

image.png

节点类：

class Node(object):
    """定义一个节点类"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

前面已经定义了节点类，那么现在开始定义单链表类：
这里注意单链表类要做的就是将各个节点给串到一起。而且我们知道单链表是有一个头节点的，那么当传如空的节点的时候，单链表类产生的实例的头节点就指向了None。传入实例话的Node节点之后，那么我们的__head就指向了node。

class SingleLinkedList(object):
    """定义单链表的类"""

    def __init__(self, node=None):
        self.__head = node
        if node:
            node.next = node

    def is_empty(self):
        """链表是不是空的"""
        return self.__head == None

    def length(self):
        """链表的长度，用游标cur来指向扫过的节点，用count来记录走节点的个数
           终止条件就是cur.next指向的是None，那么就结束了，还可以写成其他的方式。
        """
        cur = self.__head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def traverse(self):
        """遍历整个链表，和求链表的长度思想一样的"""
        cur = self.__head
        while cur:
            print(cur.elem, end =" ")

            cur = cur.next
        print()

    def add(self, item):
        """头部添加元素：注意先让node指向链表，然后再让__head指向node，这样就完成"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        """
           链表的尾添加元素，先判断链表是不是空的，是则直接让头节点指向node。
           不为空就一直走，找到最后一个节点，让它指向添加的node。
        """
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """链表的pos位置插入元素，头部和尾部添加直接调用方法"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                pre = pre.next

            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """删除节点，先找到元素，然后进行删除"""
        cur = self.__head
        pre = None
        while cur:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        """查找节点是不是存在，遍历过程中找到item存在元素区就是True，否则继续找"""
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

下面我们运行一下来看看：

if __name__ == '__main__':
    sll = SingleLinkedList()
    print(sll.is_empty())       # True
    print(sll.length())         # 0

    sll.append(1)
    print(sll.is_empty())       # False
    print(sll.length())         # 1

    sll.append(2)
    sll.add(1000)
    sll.append(3)
    sll.append(4)
    sll.append(5)
    sll.append(6)
    sll.traverse()                # 1000 1 2 3 4 5 6

    sll.insert(-1,7)
    sll.traverse()                # 7 1000 1 2 3 4 5 6 
    sll.insert(2,50)
    sll.traverse()                # 7 1000 50 1 2 3 4 5 6
    sll.insert(15,100)
    sll.traverse()                # 7 1000 50 1 2 3 4 5 6 100
    sll.remove(100)
    sll.traverse()                # 7 1000 50 1 2 3 4 5 6 
    sll.remove(7)
    sll.traverse()                # 1000 50 1 2 3 4 5 6 
    sll.remove(100)
    sll.traverse()               # 1000 50 1 2 3 4 5 6 

    print(sll.search(8))        # False
    print(sll.search(1))        # True 

链表和顺序表的对比

操作	顺序表	链表
访问	O(1)	O(n)
头部插入和删除	O(n)	O(1)
中间插入和删除	O(n)	O(n)
尾部插入和删除	O(1)	O(n)

在实现链表的过程中，我们可以发现，链表耗时表现在了遍历查找上面。杀出和插入操作本身的时间复杂度就是O(1)。顺序表查找很快，耗时表现在了拷贝和覆盖上面。

三、单向循环链表

单向循环链表是单链表的一个变形，表现为链表中的最后一个节点的连接区不再是None，而是指向了链表的头节点。

单向循环链表

代码实现
节点类：

class Node(object):
    """定义一个节点类，具有数据区和链接区，这个是不改变的"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

单向循环链表类

class SingleCycledLinkedList(object):
    """定义单像循环链表的类"""
    def __init__(self, node=None):
        self.__head=node
        if node:
            node.next=node

    def is_empty(self):
        """链表是不是空的，和单链表情况一样"""
        return self._head==None

    def length(self):
        """链表的长度，由于尾节点指向了首节点，判断条件要变为尾节点是不是指向头节点的"""
        if self.is_empty():
            return 0
        cur = self.__head
        count = 1
        while cur.next!=self.__head:
            count+=1
            cur = cur.next
        return count

    def traverse(self):
        """遍历整个链表，和求长度的时候是一样的。"""
        if self.is_empty():
            return 
        cur = self.__head 
        while cur.next !=self.__head: 
            print (cur.elem，end="") 
            cur = cur.next
        print(cur.elem)

    def add(self, item):
        """链表的头部添加元素"""
        node=Node(item)
        if self.is_empty(): #判断一下链表是不是空的特殊情况
            self.__head = node
            node.next = node
        else: #链表不是空的时候，我们先找到尾节点
            cur= self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next= self.__head
     
    def append(self, item):
        """链表的尾添加元素"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next!=self.__head: 
                cur = cur.next
            node.next=self.__head
            cur.next = node
     
    def insert(self, pos, item):
        """链表的pos位置插入元素，和单链表的形式一样"""
        if pos<=0:
            self.add(item)
        elif pos>(self.length()-1)
            self.append(item)
        else:
            pre = self.__head
            count= 0
            while count<pos-1:
                count+=1
                pre= pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """删除节点"""
        if self.is_empty():
            return
        cur =self.__head
        pre=None

        while cur.next != self.__head:
            if cur.elem ==self.__head:
                if cur == self.__head:
                    rear =self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                        self.__head = cur.next
                        rear.next= self.__head
                else:
                    pre.next = cur.next
            else:
                pre = cur
                cur = cur.next
        if cur.elem == item:
            if cur == self.__head:
                self.__head = None
            else:
                pre.next =self.__head  
             
    def search(self, item):
        """查找节点是不是存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem==item:
                return True
            else:
                cur=cur.next
        if cur.elem = item:
            return True
        return False

if __name__ == '__main__':
    sll = SingleCycleLinkList()
    print(sll.is_empty())       # True
    print(sll.length())         # 0

    sll.append(1)
    print(sll.is_empty())       # False
    print(sll.length())         # 1

    sll.append(2)
    sll.add(1000)
    sll.append(3)
    sll.append(4)
    sll.append(5)
    sll.append(6)
    sll.traverse()              # 1000 1 2 3 4 5 6

    sll.insert(-1,7)
    sll.traverse()              # 7 1000 1 2 3 4 5 6
    sll.insert(2,50)
    sll.traverse()              # 7 1000 50 1 2 3 4 5 6
    sll.insert(15,100)
    sll.traverse()              # 7 1000 50 1 2 3 4 5 6 100
    sll.remove(100)
    sll.traverse()              # 7 1000 50 1 2 3 4 5 6
    sll.remove(7)
    sll.traverse()              # 1000 50 1 2 3 4 5 6
    sll.remove(100)
    sll.traverse()              # 1000 50 1 2 3 4 5 6

    print(sll.search(8))        # False
    print(sll.search(1))        # True

四、双向链表

双向链表是一种更加复杂的一种链表。表现为：每个节点有两个连接区，一个指向前一个节点，当此节点为第一个节点的时候，它的指向为空。另外一个指向下一个节点，当此节点为最后一个节点时，指向为空值，示意图如下：

双向链表

定义节点类

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.prev = None
        self.next = None

定义双向链表类

class DoubleLinkList(object):
    """双链表"""
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head == None

    def length(self):
        """链表长度"""
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def traverse(self):
        """遍历整个链表"""
        cur = self.__head
        while cur:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

    def add(self, item):
        """链表头部添加元素，头插法"""
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node

    def append(self, item):
        """链表尾部添加元素, 尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        """指定位置添加元素
        :param  pos 从0开始
        """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            # 当循环退出后，cur指向pos位置
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

    def remove(self, item):
        """删除节点"""
        cur = self.__head
        while cur:
            if cur.elem == item:
                # 先判断此结点是否是头节点
                # 头节点
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:
                        # 判断链表是否只有一个结点
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    ll = DoubleLinkList()
    print(ll.is_empty())      # True
    print(ll.length())        # 0

    ll.append(1)
    print(ll.is_empty())      # False
    print(ll.length())        # 1

    ll.append(2)
    ll.add(1000)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)

    ll.insert(-1, 9)
    ll.traverse()            # 9 1000 1 2 3 4 5 6
    ll.insert(3, 100)
    ll.traverse()            # 9 1000 1 100 2 3 4 5 6
    ll.insert(10, 200)
    ll.traverse()            # 9 1000 1 100 2 3 4 5 6 200
    ll.remove(100)
    ll.traverse()            # 9 1000 1 2 3 4 5 6 200
    ll.remove(9)
    ll.traverse()            # 1000 1 2 3 4 5 6 200
    ll.remove(200)
    ll.traverse()            # 1000 1 2 3 4 5 6

五、LeetCode题目部分

链表类的题目在此：LeetCode链表类题目
首先挑选的是一个常见的题目，反转一个链表，这道题出现到了许多大公司的面试中。

• LeetCode 206 反转链表
  反转一个单链表。
  示例:
  输入: 1->2->3->4->5->NULL
  输出: 5->4->3->2->1->NULL
  进阶:
  你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
  思路一：我们要实现的效果如下图所示
  时间复杂度：O(n)
  空间复杂度：O(1)

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

思路二：递归法

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head ==None or head.next==None:
            return head
        root = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return root

• 203. 移除链表元素
  思路：在链表中进行元素的删除的时候，需要找到删除目标节点的前一个节点。
  方法一：

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode: 
        #处理要删除头节点的情况，这个时候要注意有情况是head里面的都是被删除元素，后面就需要返回None
        while head and head.val==val:
            head = head.next
        if head==None:
            return None
        
        # 现在开始就是删除
        cur = head
        while cur.next:
            
            if cur.next.val==val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

方法二:
使用虚拟头节点的技术，在链表中用得非常的多。上面的解法中，我们发现了要对头节点做特殊的处理。但是当我们用上了虚拟头节点之后，我们就需要去考了这个问题了。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head
        cur = dummyHead
        while cur.next:
            if cur.next.val==val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummyHead.next

• LeetCode 24.两两交换链表中的节点
  给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
思路一：通过画图来分析这道题，

初始状态

需要注意的就是指向的顺序如下：

中间状态
结果
循环迭代一直到终止：
image.png

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = dummy = ListNode(0) #上面的绿色表示的left，用0来代表
        cur.next = head
        while cur.next and cur.next.next:
            cur.next.next.next, cur.next.next, cur.next, cur = \
            cur.next, cur.next.next.next, cur.next.next, cur.next
        return dummy.next   

• Leetcode 141
  思路：快慢指针的做法，采用了两个指针的方式，一个快走，一个慢走，然后来进行一个判断。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料：
1、https://www.cs.auckland.ac.nz/compsci105s1c/resources/ProblemSolvingwithAlgorithmsandDataStructures.pdf
2、http://interactivepython.org/runestone/static/pythonds/index.html
3、https://yq.aliyun.com/articles/630638