【左神演算法課】超經典：求兩單向鏈表交點（6種情況）

来源:http://www.cnblogs.com/xiaoxi666/archive/2017/08/17/7384470.html
-Advertisement-
Play Games

目錄 題目描述 思路 程式（C++版＆java版） 詳解 題目描述： 思路： 這道題實在是太經典，一道題裡面考察了幾個知識點： １．鏈表是否有環的判斷 ２．鏈表若有環，要找到環的入口節點 ３．兩個鏈表的多種情況分析 另外，左老師講得實在是太贊了． 程式（詳解在後面）： 詳解 先把幾種情況羅列一下： ...


目錄

題目描述

思路

程式（C++版＆java版）

詳解

題目描述：

　　

思路：

　　這道題實在是太經典，一道題裡面考察了幾個知識點：

　　　　１．鏈表是否有環的判斷

　　　　２．鏈表若有環，要找到環的入口節點

　　　　３．兩個鏈表的多種情況分析

　　另外，左老師講得實在是太贊了．

程式（詳解在後面）：

  1 //C++版，重寫了左老師的Java版
  2 #include <iostream>
  3 using namespace std;
  4 
  5 //definition for singly-linked list.
  6 struct ListNode
  7 {
  8     int val;
  9     ListNode* next;
 10     ListNode(int x) : val(x), next(NULL) {}
 11 };
 12 
 13 ListNode* getLoopNode(ListNode* head) {
 14     if (NULL == head || NULL == head->next || NULL == head->next->next)
 15         return NULL;
 16     ListNode* pSlow = head->next;
 17     ListNode* pFast = head->next->next;
 18     while (pSlow != pFast) {
 19         if (NULL == pFast->next || NULL == pFast->next->next) {
 20             return NULL;
 21         }
 22         pSlow = pSlow->next;
 23         pFast = pFast->next->next;
 24     }
 25     pFast = head; //walk again to head,and speed equal.Or pSlow
 26     while (pSlow != pFast) {
 27         pSlow = pSlow->next;
 28         pFast = pFast->next;
 29     }
 30     return pSlow;//Or pFast
 31 }
 32 
 33 ListNode* noLoop(ListNode* head1, ListNode* head2) {
 34     if (NULL == head1 || NULL == head2) {
 35         return NULL;
 36     }
 37     ListNode* cur1 = head1;
 38     ListNode* cur2 = head2;
 39     int n = 0;
 40     while (NULL != cur1->next) {
 41         ++n;
 42         cur1 = cur1->next;
 43     }
 44     while (NULL != cur2->next) {
 45         --n;
 46         cur2 = cur2->next;
 47     }
 48     if (cur1 != cur2) { //tail node
 49         return NULL;
 50     }
 51     cur1 = n > 0 ? head1 : head2;
 52     cur2 = cur1 == head1 ? head2 : head1;
 53     n = abs(n);
 54     while (n--) {
 55         cur1 = cur1->next;
 56     }
 57     while (cur1 != cur2) {
 58         cur1 = cur1->next;
 59         cur2 = cur2->next;
 60     }
 61     return cur1;//Or cur2
 62 }
 63 
 64 ListNode* bothLoop(ListNode* head1, ListNode*loop1, ListNode* head2, ListNode*loop2) {
 65     ListNode* cur1 = NULL;
 66     ListNode* cur2 = NULL;
 67     if (loop1 == loop2) {
 68         cur1 = head1;
 69         cur2 = head2;
 70         int n = 0;
 71         while (cur1 != loop1) {
 72             ++n;
 73             cur1 = cur1->next;
 74         }
 75         while (cur2 != loop2) {
 76             --n;
 77             cur2 = cur2->next;
 78         }
 79         cur1 = n > 0 ? head1 : head2;
 80         cur2 = cur1 == head1 ? head2 : head1;
 81         n = abs(n);
 82         while (n--) {
 83             cur1 = cur1->next;
 84         }
 85         while (cur1 != cur2) {
 86             cur1 = cur1->next;
 87             cur2 = cur2->next;
 88         }
 89         return cur1;//Or cur2
 90     }
 91     else {
 92         cur1 = loop1->next;
 93         while (cur1 != loop1) {
 94             if (cur1 == loop2) {
 95                 return loop1;
 96             }
 97             cur1 = cur1->next;
 98         }
 99         return NULL;
100     }
101 }
102 
103 ListNode* getIntersectNode(ListNode* head1, ListNode* head2) {
104     if (NULL == head1 || NULL == head2)
105         return NULL;
106     ListNode* loop1 = getLoopNode(head1);
107     ListNode* loop2 = getLoopNode(head2);
108     if (NULL == loop1 && NULL == loop2)
109         return noLoop(head1, head2);
110     if (NULL != loop1 && NULL != loop2)
111         return bothLoop(head1, loop1, head2, loop2);
112     return NULL;//one of them have loop,so have no intersectionNode
113 }
114 
115 int main() {
116     // 1->2->3->4->5->6->7->null
117     ListNode* head1 = new ListNode(1);
118     head1->next = new ListNode(2);
119     head1->next->next = new ListNode(3);
120     head1->next->next->next = new ListNode(4);
121     head1->next->next->next->next = new ListNode(5);
122     head1->next->next->next->next->next = new ListNode(6);
123     head1->next->next->next->next->next->next = new ListNode(7);
124 
125     // 0->9->8->6->7->null
126     ListNode* head2 = new ListNode(0);
127     head2->next = new ListNode(9);
128     head2->next->next = new ListNode(8);
129     head2->next->next->next = head1->next->next->next->next->next; // 8->6
130     cout << getIntersectNode(head1, head2)->val << endl;
131 
132 
133     // 1->2->3->4->5->6->7->4...
134     head1 = new ListNode(1);
135     head1->next = new ListNode(2);
136     head1->next->next = new ListNode(3);
137     head1->next->next->next = new ListNode(4);
138     head1->next->next->next->next = new ListNode(5);
139     head1->next->next->next->next->next = new ListNode(6);
140     head1->next->next->next->next->next->next = new ListNode(7);
141     head1->next->next->next->next->next->next->next = head1->next->next->next;// 7->4
142 
143     // 0->9->8->2...
144     head2 = new ListNode(0);
145     head2->next = new ListNode(9);
146     head2->next->next = new ListNode(8);
147     head2->next->next->next = head1->next; // 8->2
148     cout << getIntersectNode(head1, head2)->val << endl;
149 
150     // 0->9->8->6->4->5->6...
151     head2 = new ListNode(0);
152     head2->next = new ListNode(9);
153     head2->next->next = new ListNode(8);
154     head2->next->next->next = head1->next->next->next->next->next; // 8->6
155     cout << getIntersectNode(head1, head2)->val << endl;
156 
157     return 0;
158 }

 

  1 //Java版．左老師給出的代碼，很贊
  2 //package problems_2017_08_16;
  3 
  4 public class Problem_03_FindFirstIntersectNode {
  5 
  6     public static class Node {
  7         public int value;
  8         public Node next;
  9 
 10         public Node(int data) {
 11             this.value = data;
 12         }
 13     }
 14 
 15     public static Node getIntersectNode(Node head1, Node head2) {
 16         if (head1 == null || head2 == null) {
 17             return null;
 18         }
 19         Node loop1 = getLoopNode(head1);
 20         Node loop2 = getLoopNode(head2);
 21         if (loop1 == null && loop2 == null) {
 22             return noLoop(head1, head2);
 23         }
 24         if (loop1 != null && loop2 != null) {
 25             return bothLoop(head1, loop1, head2, loop2);
 26         }
 27         return null;
 28     }
 29 
 30     public static Node getLoopNode(Node head) {
 31         if (head == null || head.next == null || head.next.next == null) {
 32             return null;
 33         }
 34         Node n1 = head.next; // n1 -> slow
 35         Node n2 = head.next.next; // n2 -> fast
 36         while (n1 != n2) {
 37             if (n2.next == null || n2.next.next == null) {
 38                 return null;
 39             }
 40             n2 = n2.next.next;
 41             n1 = n1.next;
 42         }
 43         n2 = head; // n2 -> walk again from head
 44         while (n1 != n2) {
 45             n1 = n1.next;
 46             n2 = n2.next;
 47         }
 48         return n1;
 49     }
 50 
 51     public static Node noLoop(Node head1, Node head2) {
 52         if (head1 == null || head2 == null) {
 53             return null;
 54         }
 55         Node cur1 = head1;
 56         Node cur2 = head2;
 57         int n = 0;
 58         while (cur1.next != null) {
 59             n++;
 60             cur1 = cur1.next;
 61         }
 62         while (cur2.next != null) {
 63             n--;
 64             cur2 = cur2.next;
 65         }
 66         if (cur1 != cur2) {
 67             return null;
 68         }
 69         cur1 = n > 0 ? head1 : head2;
 70         cur2 = cur1 == head1 ? head2 : head1;
 71         n = Math.abs(n);
 72         while (n != 0) {
 73             n--;
 74             cur1 = cur1.next;
 75         }
 76         while (cur1 != cur2) {
 77             cur1 = cur1.next;
 78             cur2 = cur2.next;
 79         }
 80         return cur1;
 81     }
 82 
 83     public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
 84         Node cur1 = null;
 85         Node cur2 = null;
 86         if (loop1 == loop2) {
 87             cur1 = head1;
 88             cur2 = head2;
 89             int n = 0;
 90             while (cur1 != loop1) {
 91                 n++;
 92                 cur1 = cur1.next;
 93             }
 94             while (cur2 != loop2) {
 95                 n--;
 96                 cur2 = cur2.next;
 97             }
 98             cur1 = n > 0 ? head1 : head2;
 99             cur2 = cur1 == head1 ? head2 : head1;
100             n = Math.abs(n);
101             while (n != 0) {
102                 n--;
103                 cur1 = cur1.next;
104             }
105             while (cur1 != cur2) {
106                 cur1 = cur1.next;
107                 cur2 = cur2.next;
108             }
109             return cur1;
110         } else {
111             cur1 = loop1.next;
112             while (cur1 != loop1) {
113                 if (cur1 == loop2) {
114                     return loop1;
115                 }
116                 cur1 = cur1.next;
117             }
118             return null;
119         }
120     }
121 
122     public static void main(String[] args) {
123         // 1->2->3->4->5->6->7->null
124         Node head1 = new Node(1);
125         head1.next = new Node(2);
126         head1.next.next = new Node(3);
127         head1.next.next.next = new Node(4);
128         head1.next.next.next.next = new Node(5);
129         head1.next.next.next.next.next = new Node(6);
130         head1.next.next.next.next.next.next = new Node(7);
131 
132         // 0->9->8->6->7->null
133         Node head2 = new Node(0);
134         head2.next = new Node(9);
135         head2.next.next = new Node(8);
136         head2.next.next.next = head1.next.next.next.next.next; // 8->6
137         System.out.println(getIntersectNode(head1, head2).value);//output:6
138 
139         // 1->2->3->4->5->6->7->4...
140         head1 = new Node(1);
141         head1.next = new Node(2);
142         head1.next.next = new Node(3);
143         head1.next.next.next = new Node(4);
144         head1.next.next.next.next = new Node(5);
145         head1.next.next.next.next.next = new Node(6);
146         head1.next.next.next.next.next.next = new Node(7);
147         head1.next.next.next.next.next.next.next = head1.next.next.next; // 7->4
148 
149         // 0->9->8->2...
150         head2 = new Node(0);
151         head2.next = new Node(9);
152         head2.next.next = new Node(8);
153         head2.next.next.next = head1.next; // 8->2
154         System.out.println(getIntersectNode(head1, head2).value);//output:2
155 
156         // 0->9->8->6->4->5->6..
157         head2 = new Node(0);
158         head2.next = new Node(9);
159         head2.next.next = new Node(8);
160         head2.next.next.next = head1.next.next.next.next.next; // 8->6
161         System.out.println(getIntersectNode(head1, head2).value);//output:4
162         System.out.println(getIntersectNode(head2, head1).value);//note the order //output:6
163 
164     }
165 
166 }

詳解

　　先把幾種情況羅列一下：

　　

 

 

　　然後照著程式執行流程梳理思路：

　　０．判斷兩鏈表是否有環（分別找環入口結點，能找到則有環，否則無環）：

　　　　若都無環，轉入第１步（可能是情況1或2）；

　　　　若都有環，轉入第２步（可能是情況4或5或6）；

　　　　若一個有環一個無環，直接返回NULL，因為如果他們相交，是不可能一個有環一個無環的（圖中情況3）；

　　１．都無環的情況，退化到兩個無環鏈表找入口點的問題（可參見＜劍指offer＞和leetcode:Intersection of Two Linked Lists）

　　　　1.0 先判斷兩條鏈表的長度；

　　　　1.1 從頭節點開始走，更長的鏈表先走＂長度之差＂步，然後一起走，如果相遇，則為入口點（情況2）；否則無交點（情況1）

　　２．都有環的情況，這種情況還要細分:

　　　　2.0 先判斷兩鏈表環入口點是否相同，若相同，則為情況4，轉入步驟2.1；若不同，則為情況5或6，轉入2.2；

　　　　2.1 如果為上圖中情況4，我們可以把兩鏈表交點作為＂假想的尾部節點＂，然後就退化成兩個無環鏈表找交點的問題了；

　　　　2.2 為判斷兩鏈表是否有交點，我們可以從第一個環的入口節點的下一個節點開始next，如果遇到了第二個鏈表環的入口節點，則返回第一個鏈表的入口節點（情況5：題目說找出第一個相交的節點，其實我覺得返回第二個鏈表的入口節點也行）；反之，若走了一圈沒遇到第二個鏈表環的入口節點，說明兩鏈表不相交（情況6）；

　　至此，程式執行結束．設計很巧妙，要熟練掌握．


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 工作吐槽
    最近工作感覺特別操心，不是因為任務多，也不是因為有解決不了的問題，而是感覺項目團隊太懶散了。大多數員工沒有工作積極性，工作經常拖延，公司沒有獎懲措施，做得好的、及時完成工作的與那些得過且過的、經常拖延工作計劃的人一樣待遇，沒有任何區別。導致一些沒有一定毅力的好員工也逐漸被同化。 公司部門的許可權分配不 ...
  • 25個c#知識點
    網站地址：http://m.3y.uu456.com/mbp_56hl91r1rx5uqa87qrzo_1.html ...
  • 深入淺出理解python 裝飾器
    之前就瞭解到了裝飾器, 但是就會點皮毛, 而且對其調用方式感到迷茫，正好現在的項目我想優化，就想到了用裝飾器, 因此深入研究了下裝飾器.先看下代碼： 我的疑惑就是明明return 的是一個函數名，按道理來講，返回的就是一個函數地址啊！我理解有問題？隨後上網查資料，又是閉包....但是我個人對它不感冒 ...
  • Python開發【第十篇】：RabbitMQ隊列
    簡介 RabbitMQ是流行的開源消息隊列系統，用erlang語言開發。RabbitMQ是AMQP（高級消息隊列協議）的標準實現。 安裝 首先安裝erlang環境。 官網：http://www.erlang.org/ Windows版下載地址：http://erlang.org/download/o... ...
  • [ECSHOP二次開發]解決分類商品Ajax連續請求導致的數據重覆
    0x00： 首先聲明一個全局變數。 然後，在滑動處罰ajax請求的代碼處，做一個判斷。 if (control) { $('.get_more').click(); }; 這個地方是獲取數據的函數以及ajax請求的函數 0x01以上原理: 首先聲明一個全局變數設置為true，在觸發滑動時間的時候，判 ...
  • 【Spring】DispatcherServlet源碼分析
    使用過HttpServlet的都應該用過其doGet和doPost方法，接下來看看DispatcherServlet對這兩個方法的實現（源碼在DispatcherServlet的父類FrameworkServlet中）： 方法里又將邏輯交由processRequest(request, respon ...
  • Luogu P1690 貪婪的Copy
    題目描述 Copy從盧牛那裡聽說在一片叫yz的神的領域埋藏著不少寶藏，於是Copy來到了這個被劃分為個區域的神地。盧牛告訴了Copy這裡共有個寶藏，分別放在第Pi個(1<=Pi<=N)區域。Copy還得知了每個區域之間的距離。現在Copy從1號區域出發，要獲得所有的寶藏併到n號區域離開。Copy很懶 ...
  • 挖個坑，寫一個Spring+SpringMVC+Mybatis的項目
    想挖個坑督促自己練技術，有時候想到一個項目，大概想了一些要實現的功能，怎麼實現。現在覺得自己差不多能完成QQ空間的主要功能了。準備立個牌坊，寫一個類似功能的網站。並且把進度放到這裡來。 初步計劃實現以下功能 1、用戶註冊、登錄、信息修改； 2、用戶進行好友關註、推送好用動態； 3、發表日誌、評論和評 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類