基础题链表203、206

203. 移除链表元素

也可以用栈解决：（程序员小熊）

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
 8         # #1.双指针：先判断第一个结点是否等于val
 9         while head and head.val == val: #head可以为空 #所有结点都是待删结点则不会进入第二个循环
10             head = head.next
11         
12         pre, cur = head, head
13 
14         while cur:
15             if cur.val == val:
16                 pre.next = cur.next
17             else:
18                 pre = cur
19             cur = cur.next
20 
21         return head
22 
23         #虚拟头节点（哨兵）可以不需要先判断头节点是否为待删的结点 这个更快一点
24         #在头节点前面加一个虚拟结点，这样头节点变成了普通结点，返回的虚拟结点的下一个结点
25         dummyHead = ListNode(-1,head) #保存虚拟头节点
26         cur = dummyHead #进行删除操作
27 
28         while cur.next: #先判断不为空
29             if cur.next.val == val:
30                 cur.next = cur.next.next #跳过
31             else:
32                 cur = cur.next #移动cur
33         
34         return dummyHead.next

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 8         #1.双指针法，在循环体中先要保存cur.next的值 ,时间效率不高
 9         # pre = None
10         # cur = head
11 
12         # while cur: #不为空时 #递归的结束条件
13         #     #先保存cur.next值
14         #     temp = cur.next
15         #     #反转
16         #     cur.next = pre 
17         #     #更新双指针
18         #     pre = cur
19         #     cur = temp
20         
21         # return pre #递归结束条件返回值
22 
23         #2.递归 逻辑和双指针一样 运行时间快
24         return self.reverse(head,None) #先给双指针初始化
25     
26     def reverse(self, cur: ListNode, pre: ListNode):
27         #递归结束条件
28         if cur == None:
29             return pre #刚开始head为空，之间返回空
30         #保存中间值
31         temp = cur.next
32         #反转
33         cur.next = pre
34         #更新递归
35         return self.reverse(temp, cur)