今天是day3,今天的內容如下：
第一題為移除鏈表元素，簡而言之為，給定一個鏈表，要求刪除所有值為val的節點并最終把頭結點輸出。
邏輯如下：
假設鏈表開頭有一系列值為 val 的節點，我們使用兩個判斷來確保可以跳過它們。
現在 cur 指向鏈表的第一個非 val 節點。
如果 cur.Next 為 nil，那么我們已經遍歷完整個鏈表，不需要再進行判斷。
否則，我們檢查 cur.Next 的值是否等于 val。如果是，我們將 cur.Next 跳過，直接指向下一個節點的下一個節點，從而刪除了值為 val 的節點。
如果 cur.Next 的值不等于 val，我們將 cur 移動到下一個節點，以便繼續遍歷鏈表。虛擬頭結點的話也僅在此邏輯上做些修改

func  removeelements(head *ListNode,val int) *ListNode {
    for head!=nil && head.Val==val{
        head = head.next
    }
    cur:=head
    for cur!=nil && cur.Next!=nil{
        if cur.Next.Val == val{
        cur.Next = cur.Next.Next
    }else{
        cur = cur.Next
    }
    }
    return head
}

法二虛擬頭結點法：

func removeElements(head *ListNode,val int) *ListNode{
    dummy:=&ListNode{}
    dummy.Next = head
    cur:=dummy
    for cur!=nil && cur.Next!=nil{
        if cur.Next.Val == val{
            cur.Next =cur.Next.Next
        }else{
            cur = cur.Next
        }
    }
    return dummy.Next
}

python虛擬頭結點法：

class solution:
    def removeElements(self,head:Option[ListNode],val:int) ->Option[ListNode]:
        dummy_head = ListNode(next = head)
        current = dummy_head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        return dummy_head.next

第二題為構造鏈表以及定義相關方法：
用go語言實現:

type MyLinkedList struct{
    dummy *Node
}
type Node struct{
    Val int
    Next *Node
    Pre *Node
}

func Constructor() MyLinkedList {
    rear := &Node{
        Val:-1,
        Next:nil,
        Pre:nil,
    }
    rear.Next = rear
    rear.Pre = rear
    return MyLinkedList{rear}
}

func (this *MyLinkedList) Get(index int){
    head = this.dummy.Next
    for head!= this.dummy && index > 0{
        index--
        head = head.Next
    }
    if 0!= index {
        return -1
    }
    return head.Val
}

func (this *MyLinkedList) AddAtHead(val int) {
    dummy:=this.dummy
    node:=&Node{
        Val:val,
        Next:dummy.Next,
        Pre:dummy,
    }
    dummy.Next.Pre = node
    dummy.Next = node
}

func (this *MyLinkedList) AddAtTail(val int) {
    dummy:=this.dummy
    rear:=&Node{
        Val:val,
        Next:dummy,
        Pre:dummy.Pre,
    }
    dummy.Pre.Next = rear
    dummy.Pre = rear
}

func (this *MyLinkedList) AddAtIndex(index int,val int) {
    head:=this.dummy.Next
    for head != this.dummy && index > 0 {
        head = head.Next
        index--
    }
    if index > 0{
        return 
    }
    node:=&Node{
        Val:val,
        Next:head,
        Pre:head.Pre,
    }
    head.Pre.Next = node
    head.Pre = ndoe
}
func (this *MyLinkedList) DeleteAtIndex(index int){
    if this.dummy.Next == this.dummy {
        return
    }
    head := this.dummy.Next
    for head.Next != this.dummy&&index >0 {
        head = head.Next
        index--
    }
    if index == 0{
        head.Next.Pre = head.Pre
        head.Pre.Next = head.Next
    }
}

python版本：

class ListNode:
    def __init__(self,val-0,prev=None,next=None):
        self.val =val
        self.prev = prev
        self.next = next
class MyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def get(self,index:int) -> int:
        if index < 0 or index >= index.size:
            return -1
        if index < self.size // 2:
            current = self.head
            for i in range(index):
                current = current.next
        else:
            current = self.tail
            for i in range(self.size - index -1):
                current = current.prev
        return current.val

    def addAthead(self,val:int) -> None:
        new_node = ListNode(val,None,self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_ndoe
        self.size+=1
    
    def addAtTail(self,val:int) -> None:
        new_ndoe=ListNode(val,self.tail,None)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
        self.size+=1
    
    def addAtindex(self,index:int,val:int)->None:
        if index < 0 or index > self.size:
            return
        if index == 0:
            self.addAthead(val)
        elif index == self.size:
            self.addAttail(val)
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index -1):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index):
                    current = current.prev
            new_node = ListNode(val,current,current.next)
            current.next.prev = new_node
            current.next = new_node
            self.size+=1
    
    def deleteAtindex(self,index:int) ->None:
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
            if self.head:
                self.head.prev = Noe
            else:
                self.tail = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index -1):
                    current = current.prev
            current.prev.next = current.next
            current.next.prev = current.prev
        self.size-=1

題目三：反轉鏈表，即在一個給定鏈表中，將其順序反轉：
定義兩個指針 pre 和 cur。pre 初始化為 nil，cur 初始化為頭節點 head。
遍歷鏈表，直到 cur 為 nil，即鏈表的末尾。
在每次迭代中，首先保存 cur 的下一個節點到 next，以防止鏈表丟失。
然后將 cur.Next 指向 pre，這是反轉鏈表的關鍵步驟，它將當前節點的指向改為前一個節點。
接著，移動 pre 和 cur。將 pre 更新為當前的 cur，將 cur 更新為 next（即原來的 cur.Next）。
當 cur 為 nil 時，pre 將指向原鏈表的最后一個節點，此時鏈表已經完全反轉。
最后，返回新的頭節點 pre。
這個過程實際上是在重新排列節點的指針，而不是物理地移動節點。每次迭代都將當前節點的 Next 指針指向前一個節點，從而實現鏈表的反轉。

func reverseList(head *ListNode) *ListNode{
    var pre *ListNode
    cur:=head
    for cur!=nil{
        next:=cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

python版本：

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

python遞歸法：
即便是遞歸版本，其邏輯也仍然類似

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