官网地址:https://www.dhcode.cn/p/t_pc/goods_pc_detail/goods_detail/term_624bd804b3d39_Ac0g7V?fromH5=true&type=3&channel_id=&pro_id=term_624bd804b3d39_Ac0g7V
本内容大部分从中截图
讲了三个力扣题:203,21,86
目录
基本概念
单链表代码实现
力扣203 -----链表结点的删除
题目
思路
头节点
代码
力扣21 ----合并两个有序链表
题目:
思路
力扣86 ----链表的划分
题目
思路
代码
本系列:
基本概念
单链表代码实现
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
if __name__ == '__main__':
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
e = ListNode(5)
a.next = b
b.next = c
c.next = d
d.next = e
head = a
while head:
# 打印当前节点的值、内存地址和下一个节点的内存地址
print("val = [{}] address = [0x{:x}]".format(head.val, id(head)))
if head.next: # 检查下一个节点是否存在
print("next val = [{}] next address = [0x{:x}]".format(head.next.val, id(head.next)))
head = head.next
val = [1] address = [0x1da8834ced0]
next val = [2] next address = [0x1da8834d690]
val = [2] address = [0x1da8834d690]
next val = [3] next address = [0x1da8834d750]
val = [3] address = [0x1da8834d750]
next val = [4] next address = [0x1da884c6050]
val = [4] address = [0x1da884c6050]
next val = [5] next address = [0x1da884c7210]
val = [5] address = [0x1da884c7210]
力扣203 -----链表结点的删除
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
题目
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]示例 2:
输入:head = [], val = 1 输出:[]示例 3:
输入:head = [7,7,7,7], val = 7 输出:[]提示:
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
思路
头节点
代码
# 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: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next =head
previous = dummy
current = head
while current:
if current.val == val:
previous.next = current.next
current =current.next
else:
previous =current
current =current.next
return dummy.next
力扣21 ----合并两个有序链表
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]示例 2:
输入:l1 = [], l2 = [] 输出:[]示例 3:
输入:l1 = [], l2 = [0] 输出:[0]提示:
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
思路
代码
# 定义单链表节点类
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 创建一个虚拟头结点,避免处理原头结点的特殊情况
dummy = ListNode(0)
# 使用pre指针指向当前要处理的节点的前一个节点
pre = dummy
# 当两个链表非空时,进行循环
while list1 and list2:
if list1.val < list2.val:
pre.next = list1
list1 = list1.next
else:
pre.next = list2
list2 = list2.next
pre = pre.next
# 当list1或list2为空时,将非空链表的剩余部分直接连接到合并链表末尾
# 这里只需要连接非空链表,因为循环结束时,至少有一个链表已经为空
pre.next = list1 if list1 else list2
# 返回虚拟头结点的下一个节点,即合并后链表的头节点
return dummy.next
力扣86 ----链表的划分
题目
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入:head = [1,4,3,2,5,2], x = 3 输出:[1,2,2,4,3,5]示例 2:
输入:head = [2,1], x = 2 输出:[1,2]
思路
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
small_head = ListNode(0)
greater_hred =ListNode(0)
smaller = small_head
greater = greater_hred
while head != None:
if head.val <x:
smaller.next = head
smaller =head
else:
greater.next = head
greater=head
head =head.next
smaller.next =greater_hred.next
greater.next = None
return small_head.next