{"id":344,"date":"2025-09-03T10:36:49","date_gmt":"2025-09-03T02:36:49","guid":{"rendered":"https:\/\/heyingnian.com\/?p=344"},"modified":"2025-09-03T10:37:16","modified_gmt":"2025-09-03T02:37:16","slug":"leetcode-160","status":"publish","type":"post","link":"https:\/\/heyingnian.com\/index.php\/2025\/09\/03\/leetcode-160\/","title":{"rendered":"\u76f8\u4ea4\u94fe\u8868"},"content":{"rendered":"\n


\ud83d\udd17 \u76f8\u4ea4\u94fe\u8868<\/h1>\n\n\n\n

\u9898\u76ee\u6765\u6e90\uff1a160. \u76f8\u4ea4\u94fe\u8868 – \u529b\u6263\uff08LeetCode\uff09<\/a><\/a><\/p>\n\n\n\n

\n\n\n\n

\ud83d\udccc \u9898\u76ee\u63cf\u8ff0<\/p>\n\n\n\n

\u7ed9\u4f60\u4e24\u4e2a\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9 headA<\/code> \u548c headB<\/code>\uff0c\u8bf7\u4f60\u627e\u51fa\u5e76\u8fd4\u56de\u4e24\u4e2a\u94fe\u8868\u76f8\u4ea4\u7684\u8d77\u59cb\u8282\u70b9<\/strong>\u3002\u5982\u679c\u4e24\u4e2a\u94fe\u8868\u4e0d\u5b58\u5728\u76f8\u4ea4\u8282\u70b9\uff0c\u8fd4\u56de null<\/code>\u3002<\/p>\n\n\n\n

\u56fe\u793a\u4e24\u4e2a\u94fe\u8868\u5728\u8282\u70b9\u00a0c1<\/code>\u00a0\u5f00\u59cb\u76f8\u4ea4\uff1a<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n
    \n
  • \u76f8\u4ea4\u5b9a\u4e49<\/strong>\uff1a\u4e24\u4e2a\u94fe\u8868\u5728\u67d0\u4e2a\u8282\u70b9\u00a0c<\/code>\u00a0\u5904\u201c\u5408\u5e76\u201d\uff0c\u5373\u4ece\u8be5\u8282\u70b9\u5f00\u59cb\uff0c\u540e\u7eed\u6240\u6709\u8282\u70b9\u5b8c\u5168\u5171\u4eab\uff08\u5185\u5b58\u5730\u5740\u76f8\u540c\uff09\u3002<\/li>\n\n\n\n
  • \u4fdd\u8bc1<\/strong>\uff1a\u94fe\u8868\u4e2d\u4e0d\u5b58\u5728\u73af<\/strong>\u3002<\/li>\n\n\n\n
  • \u8981\u6c42<\/strong>\uff1a\u51fd\u6570\u8fd4\u56de\u540e\uff0c\u94fe\u8868\u5fc5\u987b\u4fdd\u6301\u539f\u59cb\u7ed3\u6784<\/strong>\uff08\u4e0d\u80fd\u4fee\u6539\u6307\u9488\u7ed3\u6784\uff09\u3002<\/li>\n<\/ul>\n\n\n\n
    \n\n\n\n

    \u2705 \u793a\u4f8b\u89e3\u6790<\/p>\n\n\n\n

    \u793a\u4f8b 1<\/strong>\uff1a<\/p>\n\n\n\n

    \"\"<\/div><\/figure>\n\n\n\n
      \n
    • \u8f93\u5165\uff1aintersectVal = 8<\/code>,\u00a0listA = [4,1,8,4,5]<\/code>,\u00a0listB = [5,6,1,8,4,5]<\/code>,\u00a0skipA = 2<\/code>,\u00a0skipB = 3<\/code><\/li>\n\n\n\n
    • \u8f93\u51fa\uff1aIntersected at '8'<\/code><\/li>\n\n\n\n
    • \u89e3\u91ca\uff1a\n
        \n
      • \u94fe\u8868 A\uff1a4 \u2192 1 \u2192 8 \u2192 4 \u2192 5<\/code><\/li>\n\n\n\n
      • \u94fe\u8868 B\uff1a5 \u2192 6 \u2192 1 \u2192 8 \u2192 4 \u2192 5<\/code><\/li>\n\n\n\n
      • \u4ece\u503c\u4e3a\u00a08<\/code>\u00a0\u7684\u8282\u70b9\u5f00\u59cb\uff0c\u4e24\u4e2a\u94fe\u8868\u5171\u4eab\u540e\u7eed\u6240\u6709\u8282\u70b9\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n

        \u793a\u4f8b 2<\/strong>\uff1a<\/p>\n\n\n\n

        \"\"<\/div><\/figure>\n\n\n\n
          \n
        • \u8f93\u5165\uff1aintersectVal = 2<\/code>,\u00a0listA = [1,9,1,2,4]<\/code>,\u00a0listB = [3,2,4]<\/code>,\u00a0skipA = 3<\/code>,\u00a0skipB = 1<\/code><\/li>\n\n\n\n
        • \u8f93\u51fa\uff1aIntersected at '2'<\/code><\/li>\n\n\n\n
        • \u89e3\u91ca\uff1a\u5728\u503c\u4e3a\u00a02<\/code>\u00a0\u7684\u8282\u70b9\u5904\u76f8\u4ea4\u3002<\/li>\n<\/ul>\n\n\n\n

          \u793a\u4f8b 3<\/strong>\uff1a<\/p>\n\n\n\n

          \"\"<\/div><\/figure>\n\n\n\n
            \n
          • \u8f93\u5165\uff1aintersectVal = 0<\/code>,\u00a0listA = [2,6,4]<\/code>,\u00a0listB = [1,5]<\/code>,\u00a0skipA = 3<\/code>,\u00a0skipB = 2<\/code><\/li>\n\n\n\n
          • \u8f93\u51fa\uff1aNo intersection<\/code>\uff08\u8fd4\u56de\u00a0null<\/code>\uff09<\/li>\n\n\n\n
          • \u89e3\u91ca\uff1a\u4e24\u4e2a\u94fe\u8868\u65e0\u4ea4\u70b9\u3002<\/li>\n<\/ul>\n\n\n\n
            \n\n\n\n

            \u26a0\ufe0f \u63d0\u793a<\/p>\n\n\n\n

              \n
            • listA<\/code>\u00a0\u4e2d\u8282\u70b9\u6570\u76ee\u4e3a\u00a0m<\/code>\uff0clistB<\/code>\u00a0\u4e2d\u8282\u70b9\u6570\u76ee\u4e3a\u00a0n<\/code><\/li>\n\n\n\n
            • 1 <= m, n <= 3 * 10\u2074<\/code><\/li>\n\n\n\n
            • 1 <= Node.val <= 10\u2075<\/code><\/li>\n\n\n\n
            • 0 <= skipA <= m<\/code><\/li>\n\n\n\n
            • 0 <= skipB <= n<\/code><\/li>\n\n\n\n
            • \u82e5\u76f8\u4ea4\uff0c\u5219\u00a0intersectVal == listA[skipA] == listB[skipB]<\/code><\/li>\n<\/ul>\n\n\n\n
              \n\n\n\n

              \ud83d\udca1 \u89e3\u6cd5\uff1a\u53cc\u6307\u9488\u201c\u6d6a\u6f2b\u76f8\u9047\u201d\u6cd5 \u2014\u2014 O(m + n) \u65f6\u95f4\uff0cO(1) \u7a7a\u95f4<\/p>\n\n\n\n

              public class Solution {\n    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {\n        ListNode pA = headA;\n        ListNode pB = headB;\n        \n        while (pA != pB) {\n            pA = (pA != null) ? pA.next : headB;\n            pB = (pB != null) ? pB.next : headA;\n        }\n        \n        return pA;\n    }\n}<\/code><\/pre>\n\n\n\n
              \n\n\n\n
              \ud83d\udcca \u590d\u6742\u5ea6\u5206\u6790<\/p>\n\n\n\n
                \n
              • \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(m + n)<\/strong>\n
                  \n
                • \u6700\u574f\u60c5\u51b5\u4e0b\uff0c\u6bcf\u4e2a\u6307\u9488\u90fd\u904d\u5386\u5b8c\u81ea\u5df1\u7684\u94fe\u8868\u540e\uff0c\u518d\u904d\u5386\u5bf9\u65b9\u7684\u94fe\u8868\uff0c\u603b\u5171\u8d70\u00a0m + n<\/code>\u00a0\u6b65\u3002<\/li>\n\n\n\n
                • \u5b9e\u9645\u4e0a\uff0c\u5f53\u4e24\u4e2a\u94fe\u8868\u6709\u4ea4\u70b9\u65f6\uff0c\u4f1a\u5728\u00a0m + n<\/code>\u00a0\u6b65\u5185\u76f8\u9047\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • \u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(1)<\/strong> \u2705\n
                    \n
                  • \u4ec5\u4f7f\u7528\u4e24\u4e2a\u6307\u9488\u00a0pA<\/code>\u00a0\u548c\u00a0pB<\/code>\uff0c\u65e0\u989d\u5916\u6570\u636e\u7ed3\u6784\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                    \n\n\n\n
                    \ud83e\udde9 \u89e3\u9898\u601d\u8def<\/p>\n\n\n\n
                      \n
                    1. \u6838\u5fc3\u601d\u60f3\uff1a\u53cc\u6307\u9488\u8d70\u5b8c\u81ea\u5df1\u7684\u8def\uff0c\u518d\u8d70\u5bf9\u65b9\u7684\u8def\uff0c\u6700\u7ec8\u76f8\u9047<\/strong>\n
                        \n
                      • \u8bbe\u94fe\u8868 A \u957f\u5ea6\u4e3a\u00a0a + c<\/code>\uff08a<\/code>\u00a0\u662f\u72ec\u6709\u90e8\u5206\uff0cc<\/code>\u00a0\u662f\u516c\u5171\u90e8\u5206\uff09<\/li>\n\n\n\n
                      • \u8bbe\u94fe\u8868 B \u957f\u5ea6\u4e3a\u00a0b + c<\/code>\uff08b<\/code>\u00a0\u662f\u72ec\u6709\u90e8\u5206\uff0cc<\/code>\u00a0\u662f\u516c\u5171\u90e8\u5206\uff09<\/li>\n\n\n\n
                      • \u5982\u679c\u4e24\u4e2a\u6307\u9488\u5206\u522b\u4ece\u00a0headA<\/code>\u00a0\u548c\u00a0headB<\/code>\u00a0\u51fa\u53d1\uff0c\u5e76\u5728\u5230\u8fbe\u672b\u5c3e\u65f6\u8df3\u8f6c\u5230\u5bf9\u65b9\u7684\u5934\u8282\u70b9\uff1a\n
                          \n
                        • pA<\/code>\u00a0\u8d70\u7684\u8def\u5f84\uff1aA \u2192 null \u2192 B<\/code>\uff0c\u603b\u957f\u00a0a + c + b<\/code><\/li>\n\n\n\n
                        • pB<\/code>\u00a0\u8d70\u7684\u8def\u5f84\uff1aB \u2192 null \u2192 A<\/code>\uff0c\u603b\u957f\u00a0b + c + a<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • \u5f53\u00a0pA<\/code>\u00a0\u548c\u00a0pB<\/code>\u00a0\u90fd\u8d70\u4e86\u00a0a + b + c<\/code>\u00a0\u6b65\u65f6\uff0c\u5b83\u4eec\u4f1a\u540c\u65f6\u5230\u8fbe\u76f8\u4ea4\u70b9<\/strong>\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • \u4e3a\u4ec0\u4e48\u80fd\u76f8\u9047\uff1f<\/strong>\n
                            \n
                          • \u5982\u679c\u6709\u4ea4\u70b9\uff1a\n
                              \n
                            • pA<\/code>\u00a0\u8d70\u5b8c A \u540e\u8df3\u5230 B\uff0cpB<\/code>\u00a0\u8d70\u5b8c B \u540e\u8df3\u5230 A\u3002<\/li>\n\n\n\n
                            • \u5f53\u00a0pA<\/code>\u00a0\u8d70\u4e86\u00a0a + c + b<\/code>\u00a0\u6b65\u65f6\uff0c\u5b83\u6b63\u597d\u5728\u516c\u5171\u90e8\u5206\u7684\u8d77\u70b9\u3002<\/li>\n\n\n\n
                            • \u540c\u7406\uff0cpB<\/code>\u00a0\u4e5f\u8d70\u4e86\u00a0b + c + a<\/code>\u00a0\u6b65\uff0c\u5230\u8fbe\u540c\u4e00\u4f4d\u7f6e\u3002<\/li>\n\n\n\n
                            • \u7531\u4e8e\u00a0a + c + b = b + c + a<\/code>\uff0c\u5b83\u4eec\u4f1a\u540c\u65f6\u5230\u8fbe\u4ea4\u70b9<\/strong>\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                            • \u5982\u679c\u65e0\u4ea4\u70b9\uff1a\n
                                \n
                              • \u4e24\u4e2a\u6307\u9488\u6700\u7ec8\u90fd\u4f1a\u8d70\u5b8c\u00a0m + n<\/code>\u00a0\u6b65\uff0c\u540c\u65f6\u53d8\u4e3a\u00a0null<\/code>\uff0c\u6b64\u65f6\u00a0pA == pB == null<\/code>\uff0c\u8df3\u51fa\u5faa\u73af\uff0c\u8fd4\u56de\u00a0null<\/code>\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                              • \u4ee3\u7801\u903b\u8f91\u8be6\u89e3<\/strong>\uff1ajava\u6df1\u8272\u7248\u672cwhile<\/strong> (pA != pB) { pA = (pA != null<\/strong>) ? pA.next : headB; pB = (pB != null<\/strong>) ? pB.next : headA; }<\/code>\n
                                  \n
                                • \u5faa\u73af\u6761\u4ef6\uff1apA != pB<\/code>\uff0c\u76f4\u5230\u5b83\u4eec\u76f8\u9047\uff08\u6307\u5411\u540c\u4e00\u8282\u70b9\u6216\u90fd\u4e3a\u00a0null<\/code>\uff09<\/li>\n\n\n\n
                                • \u6307\u9488\u79fb\u52a8\u89c4\u5219\uff1a\n
                                    \n
                                  • \u5982\u679c\u00a0pA<\/code>\u00a0\u8fd8\u6ca1\u5230\u5c3e\u90e8\uff0c\u5c31\u7ee7\u7eed\u524d\u8fdb\u00a0pA.next<\/code><\/li>\n\n\n\n
                                  • \u5982\u679c\u00a0pA<\/code>\u00a0\u5230\u4e86\u5c3e\u90e8\uff08null<\/code>\uff09\uff0c\u5c31\u8df3\u5230\u00a0headB<\/code>\u00a0\u5f00\u59cb\u904d\u5386 B<\/li>\n\n\n\n
                                  • \u540c\u7406\u5904\u7406\u00a0pB<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                  • \u6700\u7ec8\u00a0pA<\/code>\u00a0\u548c\u00a0pB<\/code>\u00a0\u4f1a\u5728\u4ea4\u70b9\u6216\u00a0null<\/code>\u00a0\u5904\u76f8\u9047\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                  • \u4e3e\u4f8b\u8bf4\u660e<\/strong>\uff1a
                                    \u5bf9 A: 4\u21921\u21928\u21924\u21925<\/code>, B: 5\u21926\u21921\u21928\u21924\u21925<\/code>\uff0c\u4ea4\u70b9\u4e3a 8<\/code>\uff1a\n
                                      \n
                                    • pA<\/code>\u00a0\u8def\u5f84\uff1a4\u21921\u21928\u21924\u21925\u21925\u21926\u21921\u21928<\/code><\/li>\n\n\n\n
                                    • pB<\/code>\u00a0\u8def\u5f84\uff1a5\u21926\u21921\u21928\u21924\u21925\u21924\u21921\u21928<\/code><\/li>\n\n\n\n
                                    • \u5f53\u00a0pA<\/code>\u00a0\u548c\u00a0pB<\/code>\u00a0\u90fd\u8d70\u5230\u7b2c 9 \u4e2a\u8282\u70b9\u65f6\uff0c\u90fd\u5728\u00a08<\/code>\u00a0\u5904\u76f8\u9047 \u2705<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                    • \u8fb9\u754c\u5904\u7406<\/strong>\uff1a\n
                                        \n
                                      • \u4efb\u4e00\u94fe\u8868\u4e3a\u7a7a\uff1apA<\/code>\u00a0\u6216\u00a0pB<\/code>\u00a0\u4e00\u5f00\u59cb\u5c31\u4e3a\u00a0null<\/code>\uff0c\u6700\u7ec8\u90fd\u4f1a\u8d70\u5230\u00a0null<\/code>\uff0c\u8fd4\u56de\u00a0null<\/code>\u3002<\/li>\n\n\n\n
                                      • \u65e0\u4ea4\u70b9\uff1a\u4e24\u4e2a\u6307\u9488\u6700\u7ec8\u90fd\u4e3a\u00a0null<\/code>\uff0c\u5faa\u73af\u7ed3\u675f\uff0c\u8fd4\u56de\u00a0null<\/code>\u3002<\/li>\n\n\n\n
                                      • \u6709\u4ea4\u70b9\uff1a\u5fc5\u5728\u4ea4\u70b9\u5904\u76f8\u9047\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
                                        \ud83d\udd17 \u76f8\u4ea4\u94fe\u8868 \u9898\u76ee\u6765\u6e90\uff1a160. \u76f8\u4ea4\u94fe\u8868 – \u529b\u6263\uff08LeetCode\uff09 \ud83d\udccc \u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e24\u4e2a\u5355 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,38],"tags":[14,51],"class_list":["post-344","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-linked_list","tag-algorithm","tag-linked_list"],"_links":{"self":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/comments?post=344"}],"version-history":[{"count":1,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/344\/revisions"}],"predecessor-version":[{"id":349,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/344\/revisions\/349"}],"wp:attachment":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/media?parent=344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/categories?post=344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/tags?post=344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}