代码随想录算法训练营第三天 | 链表整理

对于Python来说，最基础的链表定义如下：

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

链表的元素不一定像数组一样存放在连续的位置，通过self.val确认当前指针指向的值，self.next指向链表的下一个元素

链表相关操作：

1. 定义空链表：
   在创建空链表的时候，只需要将链表头节点变量设置为空连接就可以，Python中设置为None。

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

2. 建立线性链表：
   取第一个数据元素作为链表的表头，后面元素需要依靠ListNode生成链节点，再用next指向定义的下一个链节点。

# 根据 data 初始化一个新链表
def create(self, data):
    if not data:
        return
    self.head = ListNode(data[0])
    cur = self.head
    for i in range(1, len(data)):
        node = ListNode(data[i])
        cur.next = node  # 插入链表
        cur = cur.next  # 移动指针，为下一次加入元素做准备

3. 求线性链表的长度：
   通过for循环，让每一次指向下一节点时，对应的count加一累计。

def length(self):
    count = 0
    cur = self.head
    while cur:
        count += 1
        cur = cur.next  # 移动指针
    return count

4. 查找元素：
   沿着链节点的next指针遍历链表，如果cur.val == target ，则返回当前指针变量cur，若没有结果，则返回None

def find(self, target):
    cur = self.head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None

5.插入元素：
a. 头部插入元素：创建链节点node，node的next指向head，头节点head则指向node。

def insertFront(self, val):
    node = ListNode(val)
    node.next = self.head
    self.head = node

b. 尾部插入节点：
当cur的next不为None时，保持next指向下一个数，当cur的next为None时，表示索引到链表的尾部，此时将cur的next指向对应的node。

def inserRear(self, val):
    node = ListNode(val)
    cur = self.head
    while cur.next:
        cur = cur.next
    cur.next = node

c. 中间插入节点：
需要对cur进行索引，并累计计数器到index - 1，类似头节点插入，node.next指向cur.next，cur.next则指向node

def inserInside(self, index, val):
    node = ListNode(val)
    count = 0
    cur = self.head
    while cur and count < index - 1:
        count += 1
        cur = cur.next

    if not cur:  # 注意添加此处判断
        return 'Error'

    node.next = cur.next
    cur.next = node

6. 改变元素
   类似在中间插入元素，需要对cur进行索引，并累计计数器到index，将此处的cur.val赋值为val

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

7. 删除节点：直接让指针跳过下一个节点，指向下下个节点

# 整体逻辑
self.next = self.next.next

# 删除头节点
self.head = self.head.next

# 删除尾节点
if cur.next.next:
    cur = cur.next
cur.next = None

# 链表中间删除元素
def removeInside(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