Python数据结构-链表（Linked List）

链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

我们先来简单介绍一下链表结构的优缺点：

• 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
• 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

双向链表（Doubly Linked List）：链表的一种，也叫做双链表。它的每个链节点中有两个指针，分别指向直接后继和直接前驱。

循环链表（Circular linked list）：链表的一种。它的最后一个链节点指向头节点，形成一个环。

链表的实现与基本操作

# 链节点以及链表的结构定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinKList:
    def __init__(self):
        self.head = None

# 建立一个线性链表
def create(self, data):
    self.head = ListNode(0)        # 头节点
    cur = self.head                # 当前节点
    for i in range(len(data)):
        node = ListNode(data[i])
        cur.next = node
        cur = cur.next

# 求线性链表的长度
def length(self):
    count = 0
    cur = self.head
    while cur:
        count += 1
        cur = cur.next
    return count

# 查找元素
def find(self, val):
    cur = self.head
    while cur:
        if cur.val == val:
            return cur
        cur = cur.next
    # 查找无结果
    return None

# 链表头部插入元素
def insertFront(self, val):
    # 创建一个值为val的链节点
    node = ListNode(val)    
    # 将node节点指向头节点
    node.next = self.head
    # 将链表的头节点head指向node
    self.head = node

# 链表尾部插入元素
def insertRear(self, val):
    node = ListNode(val)
    cur = self.head
    while cur:
        cur = cur.next
    # 将链表的尾节点指向node
    cur.next = node

# 链表中间插入元素
def insertMiddle(self, index, val):
    count = 0
    cur = self.head
    # 找到待插入位置的前一个链表节点
    while cur and count < index - 1:
        count += 1
        cur = cur.next
    if not cur:
        return 'Error'
    # 先将待插入节点与后节点相连，然后前节点与插入节点相连
    node = ListNode(val)
    node.next = cur.next
    cur.next = node

# 改变元素
def change(self, index, val):
    count = 0
    cur = self.head
    while cur and count < index:
        count += 1
        cur = cur.next
    if not cur:
        return 'Error'
    # 直接赋值
    cur.val = val

# 删除链表头部的元素
def removeFront(self):
    if self.head:
        self.head = self.head.next

# 删除链表尾部的元素
def removeRear(self):
    # 对于一个节点的链表
    if not self.head.next:
        return 'Error'

    cur = self.head
    while cur.next.next:
        cur = cur.next
    cur.next = None

# 删除链表中间位置的元素
def removeMiddle(self, index):
    count = 0
    cur = self.head

    while cur.next and count < index - 1:
        count += 1
        cur = cur.next
    if not cur:
        return 'Error'
    
    del_node = cur.next
    cur.next = del_node.next

707. 设计链表

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = ListNode(0)

    # 获取链表元素
    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.head
        for _ in range(index+1):
            cur = cur.next
        return cur.val

    # 头节点插入
    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    # 尾节点插入
    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    # 指定位置插入元素
    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        if index < 0:
            index = 0
        # 链表长度加1
        self.size += 1
        pre = self.head
        for _ in range(index):
            pre = pre.next
        # 插入的节点
        addNode = ListNode(val)
        addNode.next = pre.next
        pre.next = addNode

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        pre = self.head
        for _ in range(index):
            pre = pre.next
        # 需要删除index位置的元素
        pre.next = pre.next.next

206. 反转链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

• 使用迭代

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        cur = head
        while cur:
            next = cur.next     # 第三个节点
            cur.next = prev     # 第二个节点指向第一个节点
            prev = cur          # 前一个节点 prev 移动到当前节点
            cur = next          # 当前节点继续向后遍历到 next 位置（遍历当前节点）
        return prev             # 最后返回新的头节点

• 使用递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:   #递归终止条件
            return head
        p = self.reverseList(head.next)
        # A --> B --> C(none)   ==> B --> A --> C(none)
        head.next.next = head
        head.next = None
        return p

203. 移除链表元素

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

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

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 链表初始化头节点
        newNode = ListNode(0, head)
        newNode.next = head

        prev = newNode       # 头节点
        cur = head
        while cur:
            if cur.val == val:
                prev.next = cur.next
                cur = cur.next
            else:
                prev = prev.next
                cur = cur.next
        return newNode.next