链表基础#

1
class Solution:
2
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
3
        # 设置虚拟头结点，next 指向原链表头节点
4
        dummy = ListNode(next=head)
5
        cur = dummy
6
        # 遍历链表，删除值等于 val 的节点
7
        while cur.next:
8
            if cur.next.val == val:
9
                # 删除节点：跳过当前节点的下一个节点
10
                cur.next = cur.next.next
11
            else:
12
                # 只有不删除时才移动指针
13
                cur = cur.next
14
        return dummy.next

1
# 定义双向链表节点
2
class ListNode:
3
    def __init__(self, val=0, prev=None, next=None):
4
        self.val = val
5
        self.prev = prev
6
        self.next = next
7

8
class MyLinkedList:
9
    def __init__(self):
10
        # 初始化为空链表
11
        self.head = None
12
        self.tail = None
13
        self.length = 0
14

15
    def get(self, index: int) -> int:
16
        # index 的范围 [0, length - 1]
17
        if index < 0 or index >= self.length:
18
            return -1
19
        # 从头节点开始遍历
20
        cur = self.head
21
        for _ in range(index):
22
            cur = cur.next
23
        return cur.val
24

25
    def addAtHead(self, val: int) -> None:
26
        new_node = ListNode(val)
27
        if self.length == 0:
28
            # 空链表，head 和 tail 都指向新节点
29
            self.head = self.tail = new_node
30
        else:
31
            new_node.next = self.head
32
            self.head.prev = new_node
33
            self.head = new_node
34
        self.length += 1
35

36
    def addAtTail(self, val: int) -> None:
37
        new_node = ListNode(val)
38
        if self.length == 0:
39
            # 空链表，head 和 tail 都指向新节点
40
            self.head = self.tail = new_node
41
        else:
42
            new_node.prev = self.tail
43
            self.tail.next = new_node
44
            self.tail = new_node
45
        self.length += 1
46

47
    def addAtIndex(self, index: int, val: int) -> None:
48
        # index 的范围 [0, length]
49
        if index < 0 or index > self.length:
50
            return
51
        if index == 0:
52
            self.addAtHead(val)
53
        elif index == self.length:
54
            # self.length - 1 指向尾节点，而是 self.length 指向新节点的尾部
55
            self.addAtTail(val)
56
        else:
57
            # 插入到中间位置
58
            cur = self.head
59
            for _ in range(index - 1):
60
                cur = cur.next
61
            new_node = ListNode(val)
62
            new_node.next = cur.next
63
            new_node.prev = cur
64
            cur.next.prev = new_node
65
            cur.next = new_node
66
            self.length += 1
67

68
    def deleteAtIndex(self, index: int) -> None:
69
        # index 的范围 [0, length - 1]
70
        if index < 0 or index >= self.length:
71
            return
72
        if self.length == 1:
73
            # ⚠️ 容易被忽视，删除唯一节点
74
            self.head = self.tail = None
75
        elif index == 0:
76
            # 删除头节点
77
            self.head = self.head.next
78
            self.head.prev = None
79
        elif index == self.length - 1:
80
            # 删除尾节点
81
            self.tail = self.tail.prev
82
            self.tail.next = None
83
        else:
84
            # 删除中间节点
85
            cur = self.head
86
            for _ in range(index):
87
                cur = cur.next
88
            cur.prev.next = cur.next
89
            cur.next.prev = cur.prev
90
        self.length -= 1

1
class Solution:
2
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        prev, cur = None, head
4
        # 当 cur 为 None 时，prev 指向链表的最后一个节点，即新的头节点
5
        while cur:
6
            next_node = cur.next       # 暂存下一节点
7
            cur.next = prev            # 当前节点指向前一节点（反转）
8
            prev = cur
9
            cur = next_node
10
        return prev

1
class Solution:
2
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        return self.reverse(head, None)
4

5
    def reverse(self, cur: Optional[ListNode], prev: Optional[ListNode]) -> Optional[ListNode]:
6
        if not cur:
7
            return prev
8
        temp = cur.next               # 暂存下一节点
9
        cur.next = prev              # 当前节点指向前一节点（反转）
10
        # 新头节点是由最深层的递归调用产生的。如果不用 return 将它层层向上传递，最终就会丢失
11
        return self.reverse(temp, cur)