algorithms/092-reverse-linked-list-ii.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "played-three",
   "metadata": {},
   "source": [
    "### [反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)\n",
    "\n",
    "反转从位置`m`到`n`的链表。请使用一趟扫描完成反转。\n",
    "\n",
    "#### 说明:\n",
    "\n",
    "- `1 ≤ m ≤ n ≤ 链表长度`。\n",
    "\n",
    "#### 示例:\n",
    "```\n",
    "输入: 1->2->3->4->5->NULL, m = 2, n = 4\n",
    "输出: 1->4->3->2->5->NULL\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "korean-somalia",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "    \n",
    "    @staticmethod\n",
    "    def fromList(nums: List[int]):\n",
    "        n, head = len(nums), ListNode(nums[0])\n",
    "        node = head\n",
    "        for i in range(1, n):\n",
    "            node.next = ListNode(nums[i])\n",
    "            node = node.next\n",
    "        return head\n",
    "    \n",
    "    def __str__(self):\n",
    "        s = str(self.val)\n",
    "        node = self.next\n",
    "        while node:\n",
    "            s += \" -> \" + str(node.val)\n",
    "            node = node.next\n",
    "        return s\n",
    "\n",
    "def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:\n",
    "    dummy = ListNode(0, head)\n",
    "    t1 = dummy\n",
    "    i = 1\n",
    "    while i < m:\n",
    "        t1 = t1.next\n",
    "        i += 1\n",
    "    \n",
    "    t2 = t1.next\n",
    "    prev, curr = None, t2\n",
    "    while i <= n:\n",
    "        nxt = curr.next\n",
    "        curr.next = prev\n",
    "        prev = curr\n",
    "        curr = nxt\n",
    "        i += 1\n",
    "    \n",
    "    t1.next = prev\n",
    "    t2.next = curr\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "continuing-extension",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 4 -> 3 -> 2 -> 5\n"
     ]
    }
   ],
   "source": [
    "head = ListNode.fromList([1, 2, 3, 4, 5])\n",
    "print(reverseBetween(head, 2, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "comic-anthropology",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 -> 4 -> 3 -> 2 -> 1\n"
     ]
    }
   ],
   "source": [
    "head = ListNode.fromList([1, 2, 3, 4, 5])\n",
    "print(reverseBetween(head, 1, 5))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}