算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表

203.移除链表元素

状态：完成

个人思路：首先令head符合条件，之后判断这个head是否为空，空的话返回空节点；非空的话继续进行。令pre=head；cur = head->next，只要cur非空，就判断cur的值的情况，如果需要删除，就改变pre->next和cur；如果不需要删除就继续检查下一个。

看完讲解视频之后的想法：我认为他的分析很有逻辑性，首先判断出对于头结点和非头结点的删除方式是不一样的。这样就有两种方法可以处理，第一种就是像我那样；分别处理；还有一种就是虚拟头结点方法，这样就可以统一处理了。我忘记释放了，记得c++要释放。

206.反转链表

状态：完成

个人思路：首先判断head是不是空节点，是的话直接返回就好了。如果不是，那么就要考虑一种算法能够涵盖三种情况，一种是只有一个元素，第二种是有两个元素，第三种是有三个及以上的元素。起初我的做法是：before是空指针，cur为head，如果cur->next为空，那么就是只有一个元素，直接返回头结点。然后令after = cur->next（因为之前已经检查过非空了，所以这里没问题），所以这里就是两个元素和多个元素的情况。这种情况下，while（cur），就移动，重点是after = after->next，因为进入的时候并没有判断after，所以可能after为空，然后在这里我加了一个条件，if（after->next），才after = after->next，但是这样会出现什么问题呢，我现在也不知道。

问题出在哪里？待解决。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        pre = None
        cur = head
        nex = cur.next
        if not nex:
            return cur
        while(cur):
            cur.next = pre
            pre = cur
            cur = nex
            if(nex.next):
            
                nex = nex.next
        return pre

之后我在gpt的提示下自己想出了一种办法，就是首先判断head是不是空，是空节点就返回，不是的话，就赋值before和cur，然后while（cur.next），（不满足就return cur，和后边重合了，涵盖了只有一个元素的情况）满足就赋值after = cur.next 然后移动。当cur为最后一个元素的时候，循环被跳出，然后再额外令cur.next  = pre，最后还是返回cur；这样就把两个元素和多个元素情况统一了。这种方法我认为重点在于先检查while（cur.next），再赋值。

最后gpt告诉和看课我一种很神奇的方法，简洁优美，让我有很深刻的感触，我经常惯性上来就直接考虑特殊情况，实则或许可以先抓住核心考虑，然后再看满不满足特殊情况。

然后还有递归的方法可以实现，代码随想录中是根据双指针对应的递归，我觉得很厉害。