一、链表种类

简单列表：包含 val 和next指针

双端链表：包含val 和 pre、next指针

二、定义链表

class ListNode_handle:
    def __init__(self):
        self.cur_node = None

    def add(self, data):
        # add a new node pointed to previous node
        node = ListNode()
        node.val = data
        node.next = self.cur_node
        self.cur_node = node
        return node

    def print_ListNode(self, node):
        while node:
            print('\nnode: ', node, ' value: ', node.val, ' next: ', node.next)
            node = node.next

    def reverse(self, nodelist):
        list = []
        while nodelist:
            list.append(nodelist.val)
            nodelist = nodelist.next
        result = ListNode()
        result_handle = ListNode_handle()
        for i in list:
            result = result_handle.add(i)
        return result



# node_list = [5,3,4,1,6]
list_handle = ListNode_handle()
l1 = ListNode()
l1_list = [1, 8, 3]
for i in l1_list:
    l1 = list_handle.add(i)
l1 = list_handle.reverse(l1)
list_handle.print_ListNode(l1)

输出结果：

三、删除链表中的一个元素

删除链表中的元素思想就是找到这个元素的下一个元素赋值给需要删除的元素，然后把当前这个元素指针指向需要删除元素的后两个值

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


class Solution:
    """
    @param: head: a ListNode
    @param: val: An integer
    @return: a ListNode
    """

    def removeElements(self, head, val):
        # write your code here
        tem_head = tem = ListNode1(-1)
        head_tem = head
        # 遍历一遍链表然后发现和val不相等就加入tem后
        while head_tem:
            if head_tem.val != val:
                tem.next = head_tem
                tem = tem.next
            # 无论相不相等都需要继续遍历，
            head_tem = head_tem.next
        # 最后结尾的时候一定要加上None，否则tem的下一位很有可能还有其他元素
        tem.next = None
        return tem_head.next


head = l1
val = 3
res = Solution().removeElements(head, val)
# list_handle.print_ListNode(l1)
while l1:
    print(f'node---: {l1},value:{l1.val},next:{l1.next}')
    l1 = l1.next

输出结果：

四、如何合并两个有序链表

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

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        prehead = ListNode(-1)

        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 if l1 is not None else l2

        return prehead.next

输出结果：?