LeetCode 刷题之链表【Python实现】_超市赠品题目 python 链表实现

1. 合并两个有序链表

• 牛客
• 力扣

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例一：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例二：
输入：l1 = [], l2 = []
输出：[]

示例三：
输入：l1 = [], l2 = [0]
输出：[0]
1
2
3
4
5
6
7
8
9
10
11

题解：

哨兵节点的作用是方便得到最后的链表，即一个虚拟的头节点

from typing import Optional


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


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 设置哨兵节点（虚拟头结点），将较小的节点连接到这个哨兵节点，最后返回 prehead.next 即可
        preHead = ListNode(-1)
        
        pre = preHead	# pre 指针，用于连接链表（指针或游标）
        l1 = list1
        l2 = list2

        while l1 and l2:
            # 将值较小的的节点接到 pre 指针
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next

            pre = pre.next  # 节点移动

        if l1:
            pre.next = l1

        if l2:
            pre.next = l2

        return preHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
'
运行
运行

参考：https://blog.csdn.net/weixin_43466639/article/details/124000412

2. 移除链表元素

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题解：

# 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:
        dummy = ListNode(next=head) # 虚拟头结点或叫哨兵节点，它的下一个节点指向 head 头结点
        cur = dummy	# 相当于游标或指针，不断移动

        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next    # 若等于目标元素，将 cur.next 指向下一个节点的 next，就实现了移除节点
            else:
                cur = cur.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 反转链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]
1
2

示例 3：

输入：head = []
输出：[]
1
2

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

题解一：双指针

# 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:
        cur = head  # 头结点
        pre = None  # 前一个节点，初始为空

        while cur != None:
            tmp = cur.next  # 保存下一个节点
            cur.next = pre  # 反转，下一个节点指向前一个节点

            # 更新节点
            pre = cur   # 移动
            cur = tmp   # 移动，相当于 cur = cur.next

        return pre		# pre 最终会移动到最后一个节点，因此返回 pre 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a8zxRT02-1676560124003)(https://tva1.sinaimg.cn/large/008eGmZEly1gnrf1oboupg30gy0c44qp.gif)]

---

题解二：递归法

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(pre, cur):
            if not cur:
                return pre
            
            tmp = cur.next
            cur.next = pre
            
            return reverse(cur, tmp)
        
        return reverse(None, head)
1
2
3
4
5
6
7
8
9
10
11
12

参考：翻转链表