算法打卡Day3链表|203.移除链表元素 707.设计链表 206.反转链表

题目：203.移除链表元素

思路：

代码随想录代码随想录 (programmercarl.com)

    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while(cur.next!=None):
            if(cur.next.val == val):
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

题目：707.设计链表

思路：

代码随想录：代码随想录 (programmercarl.com)

class Node(object):
    def __init__(self, x=0):
        self.val = x
        self.next = None
 
class MyLinkedList(object):
 
    def __init__(self):
        self.head = Node()  # 空的头结点
        self.size = 0  # 链表长度
 
    def get(self, index: int) -> int:
        if(index < 0 or index >= self.size):  # 注意index从0开始
            return -1
        cur = self.head.next
        while index:
            cur = cur.next
            index -= 1
        return cur.val
 
    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head.next
        self.head.next = new_node
        self.size += 1
 
    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
        self.size += 1
 
    def addAtIndex(self, index: int, val: int) -> None:
        if index == self.size:
            self.addAtTail(val)
            return
        elif index>self.size:
            return
        elif index<0:
            self.addAtHead(val)
            return
 
        new_node = Node(val)
        cur = self.head
        while index:
            cur = cur.next
            index -=1
        new_node.next = cur.next
        cur.next = new_node
        self.size +=1
 
    def deleteAtIndex(self, index: int) -> None:
        if index<0 or index>=self.size:
            return
        cur = self.head
        while index:
            cur = cur.next
            index -= 1
        cur.next = cur.next.next
        self.size -= 1

题目：206.反转链表

思路：

1. 双指针

代码随想录：代码随想录 (programmercarl.com)

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

2. 递归：

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

总结：
题目看着很简单，但是写的时候中间经常出现一些小问题，需要温故而知新