力扣算法-链表.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cf1e4541",
   "metadata": {},
   "source": [
    "### 链表的定义"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20491dc4",
   "metadata": {},
   "source": [
    "链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在 Python 中，可以使用类来定义链表节点，并实现链表的基本操作"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b246d9f",
   "metadata": {},
   "source": [
    "#### 定义链表节点类 (ListNode)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddbc6ef9",
   "metadata": {},
   "source": [
    "**链表节点类**用于表示链表中的每一个节点。每个节点包含**数据**和指向下一个节点的**指针**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2bcfbb9",
   "metadata": {},
   "source": [
    "##### 定义和初始化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0dad907",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val  # val：存储节点的值\n",
    "        self.next = next  # next：存储指向下一个节点的指针，默认为 None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "892a2a25",
   "metadata": {},
   "source": [
    "当创建一个新的节点时，需要知道它的值，并且可以选择性地指定下一个节点（如果没有指定，下一个节点默认为 None）。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d71c6f1",
   "metadata": {},
   "source": [
    "##### 示例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f1faf56a",
   "metadata": {},
   "outputs": [],
   "source": [
    "node1 = ListNode(1)\n",
    "node2 = ListNode(2)\n",
    "node1.next = node2  # node1 指向 node2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7c97c29",
   "metadata": {},
   "source": [
    "#### 定义链表及其基本操作(LinkedList)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc44de91",
   "metadata": {},
   "source": [
    "**链表类**用于管理链表，包含对链表的各种操作，比如插入、删除、查找等。\n",
    "\n",
    "链表类需要有一个头节点来表示整个链表的起始位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1e35a4f",
   "metadata": {},
   "source": [
    "##### 定义和初始化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51859812",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # 链表的头节点，初始为空"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c75ef42f",
   "metadata": {},
   "source": [
    "head：存储链表的头节点，初始为 None，表示链表为空。\n",
    "\n",
    "链表类不需要知道每个节点的值或指针，它只需要一个头节点来管理整个链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a46e6ff3",
   "metadata": {},
   "source": [
    "#### 示例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d2c8bbc",
   "metadata": {},
   "outputs": [],
   "source": [
    "linked_list = LinkedList()  # 创建一个空链表\n",
    "linked_list.head = ListNode(1)  # 设置链表的头节点\n",
    "linked_list.head.next = ListNode(2)  # 头节点指向第二个节点"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73bfca96",
   "metadata": {},
   "source": [
    "#### 链表完整示例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "38febfa9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 2 -> 3 -> None\n"
     ]
    }
   ],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # 链表的头节点\n",
    "\n",
    "    def append(self, val):\n",
    "        \"\"\"在链表末尾添加一个节点\"\"\"\n",
    "        new_node = ListNode(val)\n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        last = self.head\n",
    "        while last.next:\n",
    "            last = last.next\n",
    "        last.next = new_node\n",
    "\n",
    "    def print_list(self):\n",
    "        \"\"\"打印链表中的所有节点\"\"\"\n",
    "        current = self.head\n",
    "        while current:\n",
    "            print(current.val, end=\" -> \")\n",
    "            current = current.next\n",
    "        print(\"None\")\n",
    "\n",
    "# 示例使用\n",
    "linked_list = LinkedList()\n",
    "linked_list.append(1)\n",
    "linked_list.append(2)\n",
    "linked_list.append(3)\n",
    "linked_list.print_list()  # 输出: 1 -> 2 -> 3 -> None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63b4c7c2",
   "metadata": {},
   "source": [
    "#### **节点类**和**链表类**的区别"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7a59ab0",
   "metadata": {},
   "source": [
    "①职责不同：\n",
    "\n",
    "**节点类 (ListNode)**：负责存储单个节点的数据和指针，表示链表中的一个元素。\n",
    "\n",
    "**链表类 (LinkedList)**：负责管理整个链表，包含链表的头节点，并提供对链表进行各种操作的方法。\n",
    "\n",
    "②初始化内容不同：\n",
    "\n",
    "**节点类**：需要初始化节点的值和指向下一个节点的指针。\n",
    "\n",
    "**链表类**：只需要初始化链表的头节点，其他操作在方法中进行。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "834bc3cc",
   "metadata": {},
   "source": [
    "### 链表常用操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c0f3036d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([1, 2, 3])\n",
      "deque([1, 2, 99, 3])\n"
     ]
    }
   ],
   "source": [
    "# 导入 collections 模块中的 deque 类\n",
    "from collections import deque\n",
    "\n",
    "# 定义一个名为 Test 的类\n",
    "class Test1:\n",
    "    # 在 Test 类中定义一个名为 test 的方法\n",
    "    def test(self):\n",
    "        \n",
    "        \"\"\"创建链表\"\"\"\n",
    "        # 创建一个双端队列（deque）对象并赋值给变量 linkedlist        \n",
    "        linkedlist = deque() \n",
    "        \n",
    "        \"\"\"末尾添加元素\"\"\"\n",
    "        # 向双端队列的末尾添加元素 1,2,3\n",
    "        linkedlist.append(1)        \n",
    "        linkedlist.append(2)\n",
    "        linkedlist.append(3)\n",
    "        \n",
    "        # 打印双端队列的内容\n",
    "        print(linkedlist)\n",
    "        \n",
    "        \"\"\"指定位置添加元素\"\"\"\n",
    "        linkedlist.insert(2,99)\n",
    "        print(linkedlist)        \n",
    "        \n",
    "# 创建 Test 类的一个实例，赋值给变量 test_instance\n",
    "test_instance = Test1()\n",
    "\n",
    "# 调用 test_instance 对象的 test 方法\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c9ad3bbf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "class Test2:\n",
    "    def test(self):              \n",
    "        linkedlist = deque() \n",
    "        linkedlist.append(1) \n",
    "        linkedlist.append(2) \n",
    "        linkedlist.append(3) \n",
    "        \"\"\"访问元素\"\"\"\n",
    "        element = linkedlist[2]       \n",
    "        print(element)\n",
    "              \n",
    "        \n",
    "test_instance = Test2()\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "eeca2762",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "class Test3:\n",
    "    def test(self):              \n",
    "        linkedlist = deque() \n",
    "        linkedlist.append(1) \n",
    "        linkedlist.append(5) \n",
    "        linkedlist.append(3)\n",
    "        linkedlist.insert(2,99)\n",
    "        \"\"\"搜索元素\"\"\"\n",
    "        index = linkedlist.index(99)       \n",
    "        print(index)\n",
    "              \n",
    "        \n",
    "test_instance = Test3()\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2ba658d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([1, 7, 88])\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "class Test4:\n",
    "    def test(self):              \n",
    "        linkedlist = deque() \n",
    "        linkedlist.append(1) \n",
    "        linkedlist.append(7) \n",
    "        linkedlist.append(22)\n",
    "        \"\"\"更新元素\"\"\"\n",
    "        linkedlist[2] = 88     \n",
    "        print(linkedlist)\n",
    "              \n",
    "        \n",
    "test_instance = Test4()\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "c1f221ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([1, 12, 15])\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "class Test5:\n",
    "    def test(self):              \n",
    "        linkedlist = deque() \n",
    "        linkedlist.append(1) \n",
    "        linkedlist.append(7)\n",
    "        linkedlist.append(12)\n",
    "        linkedlist.append(15)        \n",
    "        linkedlist.append(22)\n",
    "        \"\"\"删除指定元素\"\"\"\n",
    "        linkedlist.remove(22)\n",
    "        \"\"\"删除指定索引\"\"\"\n",
    "        del linkedlist[1]\n",
    "        print(linkedlist)\n",
    "              \n",
    "        \n",
    "test_instance = Test5()\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "b4fbd078",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "class Test6:\n",
    "    def test(self):              \n",
    "        linkedlist = deque() \n",
    "        linkedlist.append(1) \n",
    "        linkedlist.append(7) \n",
    "        linkedlist.append(22)\n",
    "        linkedlist.append(28)\n",
    "        \"\"\"获取链表长度\"\"\"\n",
    "        length = len(linkedlist)  \n",
    "        print(length)\n",
    "              \n",
    "        \n",
    "test_instance = Test6()\n",
    "test_instance.test()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "498f2534",
   "metadata": {},
   "source": [
    "### 设计链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ebd94f0",
   "metadata": {},
   "source": [
    "可以选择使用单链表或者双链表，设计并实现自己的链表。\n",
    "\n",
    "单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。\n",
    "\n",
    "如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。\n",
    "\n",
    "实现 MyLinkedList 类：\n",
    "\n",
    "• MyLinkedList() 初始化 MyLinkedList 对象。\n",
    "• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。\n",
    "• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。\n",
    "• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。\n",
    "• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index  的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。\n",
    "• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。\n",
    "\n",
    "示例\n",
    "输入\n",
    "[ \"MyLinkedList\", \"addAtHead\", \"addAtTail\", \"addAtIndex\", \"get\", \"deleteAtIndex\", \"get\" ]\n",
    "[ [], [1], [3], [1, 2], [1], [1], [1] ]\n",
    "输出\n",
    "[ null, null, null, null, 2, null, 3 ]\n",
    "\n",
    "解释\n",
    "MyLinkedList myLinkedList = new MyLinkedList();\n",
    "myLinkedList.addAtHead(1);\n",
    "myLinkedList.addAtTail(3);\n",
    "myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3\n",
    "myLinkedList.get(1);              // 返回 2\n",
    "myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3\n",
    "myLinkedList.get(1);              // 返回 3\n",
    "\n",
    "提示：\n",
    "\n",
    "•0 <= index, val <= 1000\n",
    "•请不要使用内置的 LinkedList 库。\n",
    "•调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "47d0251d",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Added 1 at the head.\n",
      "Added 3 at the tail.\n",
      "Added 2 at index 1.\n",
      "2\n",
      "Deleted node at index 1.\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        # 定义链表节点的结构，每个节点包含一个值和一个指向下一个节点的指针\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class MyLinkedList:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        初始化链表，头节点为空，链表长度为0\n",
    "        \"\"\"\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "\n",
    "    def get(self, index: int) -> int:\n",
    "        \"\"\"\n",
    "        获取链表中指定索引的节点的值，如果索引无效，则返回-1\n",
    "        \"\"\"\n",
    "        if index < 0 or index >= self.size:\n",
    "            return -1\n",
    "        curr = self.head\n",
    "        for _ in range(index):\n",
    "            curr = curr.next\n",
    "        return curr.val\n",
    "\n",
    "    def addAtHead(self, val: int) -> None:\n",
    "        \"\"\"\n",
    "        在链表头部插入一个值为val的节点\n",
    "        \"\"\"\n",
    "        # 创建新节点，将其指向当前头节点，然后将头节点指向新节点\n",
    "        self.head = ListNode(val, self.head)\n",
    "        self.size += 1\n",
    "        print(f\"Added {val} at the head.\")\n",
    "\n",
    "    def addAtTail(self, val: int) -> None:\n",
    "        \"\"\"\n",
    "        在链表尾部追加一个值为val的节点\n",
    "        \"\"\"\n",
    "        # 如果链表为空，直接将头节点指向新节点\n",
    "        if not self.head:\n",
    "            self.head = ListNode(val)\n",
    "        else:\n",
    "            # 否则找到链表末尾，将末尾节点的next指针指向新节点\n",
    "            curr = self.head\n",
    "            while curr.next:\n",
    "                curr = curr.next\n",
    "            curr.next = ListNode(val)\n",
    "        self.size += 1\n",
    "        print(f\"Added {val} at the tail.\")\n",
    "\n",
    "    def addAtIndex(self, index: int, val: int) -> None:\n",
    "        \"\"\"\n",
    "        在链表的指定索引处插入一个值为val的节点\n",
    "        如果索引等于链表长度，节点将被追加到末尾\n",
    "        如果索引大于长度，则节点不会被插入\n",
    "        \"\"\"\n",
    "        if index < 0 or index > self.size:\n",
    "            return\n",
    "        if index == 0:\n",
    "            # 在头部插入节点\n",
    "            self.addAtHead(val)\n",
    "        else:\n",
    "            # 在中间插入节点\n",
    "            curr = self.head\n",
    "            for _ in range(index - 1):\n",
    "                curr = curr.next\n",
    "            curr.next = ListNode(val, curr.next)\n",
    "            self.size += 1\n",
    "            print(f\"Added {val} at index {index}.\")\n",
    "\n",
    "    def deleteAtIndex(self, index: int) -> None:\n",
    "        \"\"\"\n",
    "        Delete the index-th node in the linked list, if the index is valid.\n",
    "        删除链表中指定索引的节点，如果索引有效的话\n",
    "        \"\"\"\n",
    "        if index < 0 or index >= self.size:\n",
    "            return\n",
    "        if index == 0:\n",
    "            # 删除头节点\n",
    "            self.head = self.head.next\n",
    "        else:\n",
    "            # 删除中间或尾部节点\n",
    "            curr = self.head\n",
    "            for _ in range(index - 1):\n",
    "                curr = curr.next\n",
    "            curr.next = curr.next.next\n",
    "        self.size -= 1\n",
    "        print(f\"Deleted node at index {index}.\")\n",
    "\n",
    "# 测试代码\n",
    "# 创建链表对象\n",
    "myLinkedList = MyLinkedList()\n",
    "# 在头部添加节点\n",
    "myLinkedList.addAtHead(1)\n",
    "# 在尾部添加节点\n",
    "myLinkedList.addAtTail(3)\n",
    "# 在索引1处插入节点\n",
    "myLinkedList.addAtIndex(1, 2)    # 链表变为 1->2->3\n",
    "# 获取索引1处节点的值\n",
    "print(myLinkedList.get(1))       # 返回 2\n",
    "# 删除索引1处的节点\n",
    "myLinkedList.deleteAtIndex(1)    # 现在，链表变为 1->3\n",
    "# 再次获取索引1处节点的值\n",
    "print(myLinkedList.get(1))       # 返回 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcabee3f",
   "metadata": {},
   "source": [
    "### 反转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "961b1300",
   "metadata": {},
   "source": [
    "要反转一个单链表，需要从**头节点**开始，依次将每个节点的指针指向它的前一个节点。\n",
    "为了完成这个操作，需要记录当前节点、前一个节点和下一个节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ede801e8",
   "metadata": {},
   "source": [
    "解题的基本思路：\n",
    "\n",
    "①定义三个指针：prev、curr 和 next，分别代表前一个节点、当前节点和下一个节点。\n",
    "②初始化 prev 为 None，curr 为头节点 head。\n",
    "③开始遍历链表，遍历过程中，每次都将 curr 的指针指向 prev，然后更新 prev、curr 和 next 的位置。\n",
    "④遍历完整个链表后，prev 就会指向原链表的最后一个节点，也就是反转后链表的头节点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7e396572",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 -> 4 -> 3 -> 2 -> 1 -> None\n"
     ]
    }
   ],
   "source": [
    "class ListNode: # 定义了一个 ListNode 类来表示链表节点\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def reverseLinkedList(head: ListNode) -> ListNode: # 反转链表函数\n",
    "    # 初始化 prev 为 None，curr 为头节点\n",
    "    prev = None\n",
    "    curr = head\n",
    "    \n",
    "    # 开始遍历链表\n",
    "    while curr:\n",
    "        # 保存下一个节点的指针\n",
    "        next_node = curr.next\n",
    "        # 反转当前节点的指针，指向前一个节点\n",
    "        curr.next = prev\n",
    "        # 更新 prev 和 curr 的位置，向前移动一步\n",
    "        prev = curr\n",
    "        curr = next_node\n",
    "    \n",
    "    # 循环结束后，prev 就指向反转后的头节点\n",
    "    return prev\n",
    "\n",
    "# 测试代码\n",
    "# 构建链表 [1,2,3,4,5]\n",
    "head = ListNode(1)\n",
    "current = head\n",
    "for i in range(2, 6):\n",
    "    current.next = ListNode(i)\n",
    "    current = current.next\n",
    "\n",
    "# 反转链表\n",
    "reversed_head = reverseLinkedList(head)\n",
    "\n",
    "# 输出反转后的链表\n",
    "while reversed_head:\n",
    "    print(reversed_head.val, end=\" -> \")\n",
    "    reversed_head = reversed_head.next\n",
    "print(\"None\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9865141d",
   "metadata": {},
   "source": [
    "### 移除链表元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06e7b7dd",
   "metadata": {},
   "source": [
    "要删除链表中所有值为特定值的节点，需要遍历链表，并且检查每个节点的值是否等于给定的值。如果节点的值等于给定的值，则删除该节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a27cc961",
   "metadata": {},
   "source": [
    "解题的基本思路：\n",
    "\n",
    "①使用两个指针 prev 和 curr 分别指向当前节点的前一个节点和当前节点。\n",
    "②遍历链表，当当前节点的值等于给定的值时，将前一个节点的指针指向当前节点的下一个节点，即跳过当前节点。\n",
    "③更新 prev 和 curr 指针的位置，向后移动一步。\n",
    "④当遍历完整个链表后，返回新的头节点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3496daa5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 2 -> 3 -> 4 -> 5 -> None\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def removeElements(head: ListNode, val: int) -> ListNode:\n",
    "    # 创建一个虚拟头节点，简化删除操作\n",
    "    dummy = ListNode(-1)\n",
    "    dummy.next = head\n",
    "    \n",
    "    # 初始化 prev 和 curr 指针\n",
    "    prev = dummy\n",
    "    curr = head\n",
    "    \n",
    "    # 开始遍历链表\n",
    "    while curr:\n",
    "        # 如果当前节点的值等于给定值，删除当前节点\n",
    "        if curr.val == val:\n",
    "            prev.next = curr.next\n",
    "        else:\n",
    "            # 否则更新 prev 指针\n",
    "            prev = curr\n",
    "        # 更新 curr 指针\n",
    "        curr = curr.next\n",
    "    \n",
    "    # 返回新的头节点，注意这里返回的是虚拟头节点的下一个节点\n",
    "    return dummy.next\n",
    "\n",
    "\"\"\"测试代码\"\"\"\n",
    "# 构建链表 [1,2,6,3,4,5,6]\n",
    "head = ListNode(1)\n",
    "current = head\n",
    "for val in [2, 6, 3, 4, 5, 6]:\n",
    "    current.next = ListNode(val)\n",
    "    current = current.next\n",
    "\n",
    "# 删除值为 6 的节点\n",
    "new_head = removeElements(head, 6)\n",
    "\n",
    "# 打印删除后的链表\n",
    "while new_head:\n",
    "    print(new_head.val, end=\" -> \")\n",
    "    new_head = new_head.next\n",
    "print(\"None\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d00e4abf",
   "metadata": {},
   "source": [
    "以上代码首先定义了一个 ListNode 类来表示链表节点。然后，实现了 removeElements 函数来删除链表中所有值为特定值的节点。最后，创建了一个链表，并调用 removeElements 函数来删除值为 6 的节点，并打印删除后的链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a12449f3",
   "metadata": {},
   "source": [
    "### 奇偶链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80d5cb13",
   "metadata": {},
   "source": [
    "要重新排列奇偶链表，可以将奇数位置的节点和偶数位置的节点分别提取出来，然后将偶数位置的节点连接到奇数位置的节点之后。最后，返回重排后的链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "263c34fd",
   "metadata": {},
   "source": [
    "解题的基本思路：\n",
    "\n",
    "1.使用两个指针 odd 和 even 分别指向奇数位置的节点和偶数位置的节点的头节点。\n",
    "2.遍历链表，将奇数位置的节点和偶数位置的节点分别连接成两个链表。\n",
    "3.将偶数链表连接到奇数链表的尾部。\n",
    "4.返回重排后的链表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "45543a1e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 3 -> 5 -> 2 -> 4 -> None\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def oddEvenList(head: ListNode) -> ListNode:\n",
    "    if not head or not head.next:\n",
    "        return head\n",
    "    \n",
    "    # 奇数位置的节点\n",
    "    odd = head\n",
    "    # 偶数位置的节点\n",
    "    even = head.next\n",
    "    # 偶数位置的头节点\n",
    "    even_head = even\n",
    "    \n",
    "    # 遍历链表，直到偶数位置的指针为空\n",
    "    while even and even.next:\n",
    "        # 奇数位置的下一个节点为偶数位置的下一个节点\n",
    "        odd.next = even.next\n",
    "        # 更新奇数位置的指针\n",
    "        odd = odd.next\n",
    "        # 偶数位置的下一个节点为奇数位置的下一个节点\n",
    "        even.next = odd.next\n",
    "        # 更新偶数位置的指针\n",
    "        even = even.next\n",
    "    \n",
    "    # 将偶数链表连接到奇数链表的尾部\n",
    "    odd.next = even_head\n",
    "    \n",
    "    return head\n",
    "\n",
    "# 测试代码\n",
    "# 构建链表 [1,2,3,4,5]\n",
    "head = ListNode(1)\n",
    "current = head\n",
    "for val in [2, 3, 4, 5]:\n",
    "    current.next = ListNode(val)\n",
    "    current = current.next\n",
    "\n",
    "# 重新排列链表\n",
    "new_head = oddEvenList(head)\n",
    "\n",
    "# 打印重排后的链表\n",
    "while new_head:\n",
    "    print(new_head.val, end=\" -> \")\n",
    "    new_head = new_head.next\n",
    "print(\"None\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c784a87",
   "metadata": {},
   "source": [
    "### 链表插入排序"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0952fdc2",
   "metadata": {},
   "source": [
    "插入排序的基本思想是逐一取出链表中的节点，将其插入到已经排好序的部分中，直到所有节点都处理完毕。以下是具体步骤：\n",
    "\n",
    "①创建哨兵节点（dummy）：\n",
    "创建一个哨兵节点，其 next 指向链表的头部。这样可以方便地处理头节点的插入操作。\n",
    "\n",
    "②遍历原始链表：\n",
    "\n",
    "使用两个指针 prev 和 current。prev 用于追踪要插入位置的前一个节点，current 是正在处理的节点。\n",
    "\n",
    "③插入操作：\n",
    "\n",
    "对于每个 current 节点，从 dummy 节点开始，找到合适的位置进行插入。\n",
    "\n",
    "④继续遍历：\n",
    "\n",
    "插入完成后，继续处理下一个节点，直到遍历完所有节点。\n",
    "\n",
    "这种方法对每个节点都需要找到正确的插入位置，因此时间复杂度是 O(n^2)，其中 n 是链表的长度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "c94b48f4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "[-1, 0, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"创建链表节点类\"\"\"\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\"\"\"定义解决方案类\"\"\"        \n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        # 创建一个哨兵节点，指向链表的头\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        \n",
    "        # 当前节点\n",
    "        current = head\n",
    "        \n",
    "        while current and current.next:\n",
    "            if current.val <= current.next.val:\n",
    "                # 如果当前节点的值小于等于下一个节点的值，继续向前走\n",
    "                current = current.next\n",
    "            else:\n",
    "                \"\"\"找到插入位置并插入节点\"\"\"\n",
    "                # 需要插入的节点\n",
    "                to_insert = current.next\n",
    "                # 从哨兵节点开始\n",
    "                prev = dummy\n",
    "                # 找到插入的位置\n",
    "                while prev.next.val <= to_insert.val:\n",
    "                    prev = prev.next\n",
    "                # 执行插入操作\n",
    "                current.next = to_insert.next\n",
    "                to_insert.next = prev.next\n",
    "                prev.next = to_insert\n",
    "        \n",
    "        return dummy.next\n",
    "\n",
    "# 辅助函数：将列表转换为链表\n",
    "def list_to_linkedlist(lst):\n",
    "    dummy = ListNode(0)\n",
    "    current = dummy\n",
    "    for val in lst:\n",
    "        current.next = ListNode(val)\n",
    "        current = current.next\n",
    "    return dummy.next\n",
    "\n",
    "# 辅助函数：将链表转换为Python列表-用于验证结果\n",
    "def linkedlist_to_list(node):\n",
    "    lst = []\n",
    "    while node:\n",
    "        lst.append(node.val)\n",
    "        node = node.next\n",
    "    return lst\n",
    "\n",
    "# 测试示例\n",
    "input_list = [4, 2, 1, 3]\n",
    "head = list_to_linkedlist(input_list)\n",
    "solution = Solution()\n",
    "sorted_head = solution.insertionSortList(head)\n",
    "print(linkedlist_to_list(sorted_head))  # 输出: [1, 2, 3, 4]\n",
    "\n",
    "input_list = [-1, 5, 3, 4, 0]\n",
    "head = list_to_linkedlist(input_list)\n",
    "sorted_head = solution.insertionSortList(head)\n",
    "print(linkedlist_to_list(sorted_head))  # 输出: [-1, 0, 3, 4, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f63b264",
   "metadata": {},
   "source": [
    "### 合并两个有序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6dbbfb0d",
   "metadata": {},
   "source": [
    "①定义链表节点类：\n",
    "需要一个'ListNode'类来表示链表中的节点。每个节点包含一个值 (val) 和指向下一个节点的指针 (next)。\n",
    "\n",
    "②定义合并函数：\n",
    "将在'Solution'类中定义一个方法'mergeTwoLists'，用于合并两个有序链表。使用一个哨兵节点（dummy node）来简化链表的合并操作。\n",
    "\n",
    "③合并过程：\n",
    "• 使用两个指针'l1'和'l2'分别指向两个链表的头节点。\n",
    "• 比较'l1'和'l2'当前节点的值，将较小的节点连接到结果链表中，并将相应指针向前移动。\n",
    "• 继续这一过程直到其中一个链表为空。\n",
    "• 将剩余的链表连接到结果链表的末尾。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "2070b470",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"定义链表节点类\"\"\"\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "73dd0231",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"定义解决方案类\"\"\"\n",
    "from typing import Optional\n",
    "\n",
    "class Solution:\n",
    "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 创建一个哨兵节点，简化链表合并操作\n",
    "        dummy = ListNode()\n",
    "        # 当前指针\n",
    "        current = dummy\n",
    "        \n",
    "        # 遍历两个链表\n",
    "        while list1 and list2:\n",
    "            if list1.val <= list2.val:\n",
    "                # 将 list1 的当前节点连接到结果链表\n",
    "                current.next = list1\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                # 将 list2 的当前节点连接到结果链表\n",
    "                current.next = list2\n",
    "                list2 = list2.next\n",
    "            # 移动结果链表的当前指针\n",
    "            current = current.next\n",
    "        \n",
    "        # 将剩余的链表连接到结果链表的末尾\n",
    "        if list1:\n",
    "            current.next = list1\n",
    "        else:\n",
    "            current.next = list2\n",
    "        \n",
    "        # 返回合并后的链表头节点\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "edc67011",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"辅助函数：将列表转换为链表\"\"\"\n",
    "def list_to_linkedlist(lst):\n",
    "    dummy = ListNode()\n",
    "    current = dummy\n",
    "    for val in lst:\n",
    "        current.next = ListNode(val)\n",
    "        current = current.next\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8c2d560c",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"辅助函数：将链表转换为列表\"\"\"\n",
    "def linkedlist_to_list(node):\n",
    "    lst = []\n",
    "    while node:\n",
    "        lst.append(node.val)\n",
    "        node = node.next\n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "58035eec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 7, 9, 12, 88]\n",
      "[]\n",
      "[0]\n"
     ]
    }
   ],
   "source": [
    "# 测试示例\n",
    "input_list1 = [1, 2, 88]\n",
    "input_list2 = [7, 9, 12]\n",
    "\n",
    "# 将列表转换为链表\n",
    "l1 = list_to_linkedlist(input_list1)\n",
    "l2 = list_to_linkedlist(input_list2)\n",
    "\n",
    "# 合并两个有序链表\n",
    "solution = Solution()\n",
    "merged_head = solution.mergeTwoLists(l1, l2)\n",
    "\n",
    "# 将合并后的链表转换为列表，并打印结果\n",
    "print(linkedlist_to_list(merged_head)) \n",
    "\n",
    "# 其他测试示例\n",
    "input_list1 = []\n",
    "input_list2 = []\n",
    "l1 = list_to_linkedlist(input_list1)\n",
    "l2 = list_to_linkedlist(input_list2)\n",
    "merged_head = solution.mergeTwoLists(l1, l2)\n",
    "print(linkedlist_to_list(merged_head)) \n",
    "\n",
    "input_list1 = []\n",
    "input_list2 = [0]\n",
    "l1 = list_to_linkedlist(input_list1)\n",
    "l2 = list_to_linkedlist(input_list2)\n",
    "merged_head = solution.mergeTwoLists(l1, l2)\n",
    "print(linkedlist_to_list(merged_head)) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6aea5f4",
   "metadata": {},
   "source": [
    "### 排序链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df3266d7",
   "metadata": {},
   "source": [
    "最优解的时间复杂度为 O(n log n)。\n",
    "一种经典的解法是使用归并排序（Merge Sort），因为归并排序在链表上实现相对容易，并且具有稳定的时间复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8adea84f",
   "metadata": {},
   "source": [
    "具体思路如下：\n",
    "\n",
    "①递归拆分：\n",
    "• 将链表一分为二，递归地对两个子链表进行排序。\n",
    "\n",
    "②合并排序：\n",
    "• 合并两个已排序的子链表，得到一个新的有序链表。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "8b1f1c0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "        # 递归结束条件：如果链表为空或只有一个节点，直接返回\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        # 分割链表\n",
    "        mid = self.get_middle(head)\n",
    "        left = head\n",
    "        right = mid.next\n",
    "        mid.next = None  # 断开链表\n",
    "\n",
    "        # 递归排序左右两部分链表\n",
    "        left_sorted = self.sortList(left)\n",
    "        right_sorted = self.sortList(right)\n",
    "        \n",
    "        # 合并两个有序链表\n",
    "        return self.merge(left_sorted, right_sorted)\n",
    "    \n",
    "    def get_middle(self, head: ListNode) -> ListNode:\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        \n",
    "        # 快慢指针找到中间节点\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "    \n",
    "    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        current = dummy\n",
    "        \n",
    "        # 合并两个有序链表\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                current.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                current.next = l2\n",
    "                l2 = l2.next\n",
    "            current = current.next\n",
    "        \n",
    "        # 将剩余的链表部分连接到结果链表的末尾\n",
    "        if l1:\n",
    "            current.next = l1\n",
    "        else:\n",
    "            current.next = l2\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ce3f6af",
   "metadata": {},
   "source": [
    "递归拆分 (sortList 方法)：\n",
    "• 使用递归的方式对链表进行拆分，直到每个子链表只有一个节点或为空。\n",
    "\n",
    "找到链表中点 (get_middle 方法)：\n",
    "• 使用快慢指针的方法找到链表的中间节点，将链表一分为二。\n",
    "\n",
    "合并排序 (merge 方法)：\n",
    "• 对两个已排序的子链表进行合并，得到一个新的有序链表。\n",
    "\n",
    "主函数：\n",
    "• 在主函数中，调用 sortList 方法开始递归地对链表进行排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "2ab06a7e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 2 -> 3 -> 4 -> 10 -> None\n"
     ]
    }
   ],
   "source": [
    "# 示例测试\n",
    "input_list = [10, 4, 2, 1, 3]\n",
    "head = ListNode(input_list[0])\n",
    "current = head\n",
    "for val in input_list[1:]:\n",
    "    current.next = ListNode(val)\n",
    "    current = current.next\n",
    "\n",
    "solution = Solution()\n",
    "sorted_head = solution.sortList(head)\n",
    "\n",
    "# 打印排序后的链表\n",
    "current = sorted_head\n",
    "while current:\n",
    "    print(current.val, end=\" -> \")\n",
    "    current = current.next\n",
    "print(\"None\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ac8487d",
   "metadata": {},
   "source": [
    "### 环形链表"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86fae1df",
   "metadata": {},
   "source": [
    "判断链表中是否存在环，一个常用的方法是使用快慢指针。\n",
    "\n",
    "• 使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。\n",
    "• 如果链表中存在环，那么快指针最终会追上慢指针，因为它每次比慢指针多走一步。\n",
    "• 如果链表中不存在环，那么快指针会先到达链表的尾部。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "cac7e4ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        # 定义快慢指针\n",
    "        slow = head\n",
    "        fast = head\n",
    "        \n",
    "        # 循环遍历链表\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next  # 慢指针每次移动一步\n",
    "            fast = fast.next.next  # 快指针每次移动两步\n",
    "            \n",
    "            # 如果快慢指针相遇，说明存在环\n",
    "            if slow == fast:\n",
    "                return True\n",
    "        \n",
    "        # 如果快指针到达链表末尾，说明不存在环\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "149f50fc",
   "metadata": {},
   "source": [
    "快慢指针：\n",
    "• 使用两个指针'slow'和'fast'，初始时都指向链表的头节点。\n",
    "\n",
    "遍历链表：\n",
    "• 在循环中，'slow'每次移动一步，'fast'每次移动两步，直到'fast'到达链表末尾。\n",
    "\n",
    "检查环：\n",
    "• 如果在遍历的过程中，'slow'和'fast'相遇，说明链表中存在环。\n",
    "\n",
    "返回结果：\n",
    "• 如果遍历结束后'fast'到达链表末尾，说明链表中不存在环，返回'False。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "8198d193",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# 示例测试\n",
    "input_list = [3, 2, 0, -4]\n",
    "pos = 1\n",
    "\n",
    "# 构建带环的链表\n",
    "head = ListNode(input_list[0])\n",
    "current = head\n",
    "cycle_node = None\n",
    "for i, val in enumerate(input_list[1:], 1):\n",
    "    current.next = ListNode(val)\n",
    "    current = current.next\n",
    "    if i == pos:\n",
    "        cycle_node = current\n",
    "\n",
    "# 将链表的尾部连接到指定位置形成环\n",
    "current.next = cycle_node\n",
    "\n",
    "solution = Solution()\n",
    "print(solution.hasCycle(head))  # 输出: True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab259253",
   "metadata": {},
   "source": [
    "示例测试中，首先创建一个链表，并且将链表的尾部连接到指定位置，形成一个环。\n",
    "然后调用'hasCycle'方法来判断链表中是否存在环，并打印结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0303983a",
   "metadata": {},
   "source": [
    "### 删除链表的倒数第N个结点"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afeafcc3",
   "metadata": {},
   "source": [
    "#### 解题思路\n",
    "\n",
    "要删除链表的倒数第 N 个节点，一种常见的方法是使用双指针。\n",
    "\n",
    "- 我们可以使用两个指针 `fast` 和 `slow`，初始时都指向链表的头节点。\n",
    "- 首先让 `fast` 指针向前移动 N 步，这样 `fast` 和 `slow` 之间相距 N 个节点。\n",
    "- 然后同时移动 `fast` 和 `slow` 指针，直到 `fast` 指针到达链表的末尾。\n",
    "- 此时 `slow` 指针指向的节点就是要删除的节点的前一个节点，我们将其指向下下个节点即可完成删除操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "756197b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)  # 创建哑节点\n",
    "        dummy.next = head\n",
    "        fast = slow = dummy  # 双指针初始都指向哑节点\n",
    "\n",
    "        # 让 fast 先向前移动 n 步\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "\n",
    "        # 同时移动 fast 和 slow 直到 fast 到达链表末尾\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "\n",
    "        # 删除 slow 后面的节点\n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e582a06",
   "metadata": {},
   "source": [
    "#### 代码解释\n",
    "- 创建了一个哑节点 `dummy`，并让其指向链表的头节点，这样可以处理删除头节点的情况。\n",
    "- 使用双指针 `fast` 和 `slow` 分别指向哑节点。\n",
    "- 首先让 `fast` 指针向前移动 N 步，这样 `fast` 和 `slow` 之间相距 N 个节点。\n",
    "- 然后同时移动 `fast` 和 `slow` 指针，直到 `fast` 指针到达链表的末尾。\n",
    "- 此时 `slow` 指针指向的节点就是要删除的节点的前一个节点，我们将其指向下下个节点即可完成删除操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7db572b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 示例测试\n",
    "input_list = [1, 2, 3, 4, 5]\n",
    "n = 2\n",
    "\n",
    "# 构建链表\n",
    "head = ListNode(input_list[0])\n",
    "current = head\n",
    "for val in input_list[1:]:\n",
    "    current.next = ListNode(val)\n",
    "    current = current.next\n",
    "\n",
    "solution = Solution()\n",
    "new_head = solution.removeNthFromEnd(head, n)\n",
    "\n",
    "# 打印删除节点后的链表\n",
    "current = new_head\n",
    "while current:\n",
    "    print(current.val, end=\" -> \")\n",
    "    current = current.next\n",
    "print(\"None\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}