D4.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 代码随想录算法训练营第四天｜ 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II ",
   "id": "c903c50c28823559"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "\n",
    "## 24. 两两交换链表中的节点 \n",
    "\n",
    "用虚拟头结点，这样会方便很多。 \n",
    "\n",
    "本题链表操作就比较复杂，注意事项: 为什么需要temp保存临时节点。\n",
    "\n",
    "题目链接: https://leetcode.com/problems/swap-nodes-in-pairs/description/\n",
    "文章讲解/视频讲解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html"
   ],
   "id": "d46c5babcdd71be1"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "画图帮助理解\n",
    "需要三个指针，交换部分的前一个节点，以及交换部分（可以用临时指针保存）"
   ],
   "id": "f34630332d372d0a"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "from typing import Optional\n",
    "\n",
    "\n",
    "# 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",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(next=head)\n",
    "        prev, first, second = dummy_head, head, None\n",
    "        # 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了\n",
    "        while first and first.next:\n",
    "            second = first.next\n",
    "            first.next = second.next\n",
    "            second.next = first\n",
    "            prev.next = second\n",
    "            prev = first\n",
    "            first = first.next\n",
    "        return dummy_head.next\n",
    "\n"
   ],
   "id": "afaade0843c5437"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 19.删除链表的倒数第N个节点  \n",
    "\n",
    "双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。\n",
    "\n",
    "题目链接: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/  \n",
    "文章讲解/视频讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html"
   ],
   "id": "27e6bf526b6f2d8b"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 快慢指针分离  \n",
    "快指针先走n步，然后快慢指针一起走，当快指针走到尾部时，慢指针就是倒数第n个节点的前一个节点。  \n",
    "当快指针指空时（第零个），慢指针的下一个节点就是要删除的节点（n+1），故间隔为(n+1)。  \n"
   ],
   "id": "e8e7fb09d1e34c62"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "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",
    "        # 创建一个虚拟节点，并将其下一个指针设置为链表的头部\n",
    "        dummy_head = ListNode(0, head)\n",
    "        \n",
    "        # 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点\n",
    "        slow = fast = dummy_head\n",
    "        \n",
    "        # 快指针比慢指针快 n+1 步\n",
    "        for i in range(n+1):\n",
    "            fast = fast.next\n",
    "        \n",
    "        # 移动两个指针，直到快速指针到达链表的末尾\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        # 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点\n",
    "        slow.next = slow.next.next\n",
    "        \n",
    "        return dummy_head.next"
   ],
   "id": "deeae848ce58b2b0"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 160. 链表相交  \n",
    "\n",
    "数值相同，不代表指针相同。\n",
    "\n",
    "题目链接: https://leetcode.com/problems/intersection-of-two-linked-lists/description/  \n",
    "文章讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html\n"
   ],
   "id": "320ab7bc0e54a606"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "取得两个链表的长度，然后让较长链表的指针先移动，使得两个链表剩余长度相等，然后一起移动，直到找到相同的节点。",
   "id": "45c1ece5a97c5e00"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "        \n",
    "        # 通过移动较长的链表，使两链表长度相等\n",
    "        if lenA > lenB:\n",
    "            headA = self.moveForward(headA, lenA - lenB)\n",
    "        else:\n",
    "            headB = self.moveForward(headB, lenB - lenA)\n",
    "        \n",
    "        # 将两个头向前移动，直到它们相交\n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        \n",
    "        return None\n",
    "    \n",
    "    def getLength(self, head: ListNode) -> int:\n",
    "        length = 0\n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "        return length\n",
    "    \n",
    "    def moveForward(self, head: ListNode, steps: int) -> ListNode:\n",
    "        while steps > 0:\n",
    "            head = head.next\n",
    "            steps -= 1\n",
    "        return head"
   ],
   "id": "2498a39d934b383b"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 142.环形链表II  \n",
    "\n",
    "算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。\n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html\n"
   ],
   "id": "85c2ac7c0dc3287c"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "分为两个步骤：\n",
    "1. 确定链表是否有环：快慢指针，快指针每次走两步。如果有环，快指针一定会追上慢指针。  \n",
    "1.1. 快指针 __相对于慢指针每次多走一步__，所以相遇时慢指针一定没有走完一圈，即`n % r != 0`。\n",
    "2. 找到环的入口：成环的节点数r一定是n的因数`n=xr`。慢指针回到head，快慢指针同步走，当快指针追上慢指针时，慢指针就是环的入口。\n"
   ],
   "id": "937b1351075a27be"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "![image](/Users/xiangzijian/Downloads/142.环形链表II（求入口）.gif)",
   "id": "cfec0e06e48180cb"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            \n",
    "            # If there is a cycle, the slow and fast pointers will eventually meet\n",
    "            if slow == fast:\n",
    "                # Move one of the pointers back to the start of the list\n",
    "                slow = head\n",
    "                while slow != fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                return slow\n",
    "        # If there is no cycle, return None\n",
    "        return None"
   ],
   "id": "d899b9be716c4f2f"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 总结 \n",
    "\n",
    "对于链表的题目，大家最大的困惑可能就是 什么使用用虚拟头结点，什么时候不用虚拟头结点？ \n",
    "一般涉及到 增删改操作，用虚拟头结点都会方便很多， 如果只能查的话，用不用虚拟头结点都差不多。 \n",
    "\n",
    "当然大家也可以为了方便记忆，统一都用虚拟头结点。\n",
    "\n",
    "https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E6%80%BB%E7%BB%93%E7%AF%87.html\n",
    "\n",
    "\n"
   ],
   "id": "b2e0016c42bb5006"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "initial_id",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    ""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}