203.移除链表元素

虚拟头结点
可以按统一的方式移除节点，否则需要考虑删除头结点和删除其他节点2种情况

注意：题目要求返回新的头结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        dummy_head = ListNode(next = head) # 构造虚拟头结点，指向头结点
        cur = dummy_head # 从虚拟头结点开始遍历

        while cur.next != None: # 链表最后一位为None
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

707.设计链表

单链表

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

class MyLinkedList:

    def __init__(self):
        self.head = ListNode() #指向虚拟头结点
        self.size = 0 #虚拟头结点，所以size为0

    def get(self, index: int) -> int:
        if 0 <= index < self.size: # 先判断index的范围，符合条件进入循环
            cur = self.head.next
            for i in range(index):
                cur = cur.next
            return cur.val
        else:
            return -1

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        if index < 0:
            index = 0
        cur = self.head
        while index:
            cur = cur.next
            index -= 1
        new_node = ListNode(val) #定义要插入的节点
        # 改变前后节点的指向
        new_node.next = cur.next
        cur.next = new_node
        # 改变长度
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if 0 <= index < self.size:
            cur = self.head
            for i in range(index):
                cur = cur.next
            cur.next = cur.next.next
            self.size -= 1

206.反转链表

方法1：迭代法
只改变链表的next指针的指向，直接将链表反转

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        cur = head
        pre = None

        while cur: # 当cur指向None，循环到了链表的最后，跳出循环
            temp = cur.next # 先保存cur的下一个位置
            cur.next = pre # 改变方向
            pre = cur # 开始向后移动pre和cur的位置，现将cur赋值给pre后，在移动cur
            cur = temp
        return pre