代码随想录算法训练营第三天| 203.移除链表元素 ， 707.设计链表 ， 206.反转链表

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

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

思路
虚拟头节点+双指针；利用pre和cur两个指针，分别指向dummy_head和dummy_head.next，while循环遍历指针，知道cur指针为None
*代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/remove-linked-list-elements/
from typing import Optional


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


class Solution:
    """
    设置虚拟头节点，并且使用cur和pre两个指针，初始化分别指向head和虚拟头节点，终止条件为cur为空
    为什么要保留pre指针，因为cur指针为移除val时，需要使用前置pre节点指向cur.next节点
    """
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(val)
        dummy_head.next = head
        cur = head
        pre = dummy_head
        while cur:
            if cur.val != val:
                pre = cur
                cur = cur.next
            else:
                pre.next = cur.next
                cur = cur.next
        return dummy_head.next


if __name__ == '__main__':
    head = ListNode(6)
    head.next = ListNode(5)
    s = Solution()
    head = s.removeElements(head,6)
    print(head.val)

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
37
38
39
40
41

707.设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • 边界条件：index小于0或者大于等于链表长度，返回-1
  • cur指向头节点，循环遍历index–，当index=0时，返回cur.val
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • 利用虚拟头节点进行节点新增，不要忘记链表长度+1
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • 利用虚拟头节点进行节点新增，不要忘记链表长度+1
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • 边界条件：index<0时，进行addAtHead(val)后，return；index=链表的长度，进行addAtTail(val)后，return；index>链表的长度，直接return；
  • 循环遍历index–，当index=0时，进行节点的插入，链表长度+1
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
  • 利用虚拟头节点，循环遍历index–进行删除
  • 链表长度-1

206.反转链表

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

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

思路
双指针法，初始化pre=None，cur=head，利用temp指针暂时存储cur.next

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/reverse-linked-list/
# Definition for singly-linked list.
from typing import Optional


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


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

if __name__ == '__main__':
    pass

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

总结

今天做链表三道题，有三点感受

1. 虚拟头节点解决了边界问题
2. 双指针的初始化，pre=dummy_head,cur=dummy_head.next
3. 手动模拟