MyException - 我的异常网
当前位置:我的异常网» C++ » 【左神人算法课】超经典:求两单向链表交点(6种情

【左神人算法课】超经典:求两单向链表交点(6种情况)

www.MyException.Cn  网友分享于:2013-08-22  浏览:0次
【左神算法课】超经典:求两单向链表交点(6种情况)

目录

题目描述

思路

程序(C++版&java版)

详解

题目描述:

  

思路:

  这道题实在是太经典,一道题里面考察了几个知识点:

    1.链表是否有环的判断

    2.链表若有环,要找到环的入口节点

    3.两个链表的多种情况分析

  另外,左老师讲得实在是太赞了.

程序(详解在后面):

  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 }

详解

  先把几种情况罗列一下:

  

 

 

  然后照着程序执行流程梳理思路:

  0.判断两链表是否有环(分别找环入口结点,能找到则有环,否则无环):

    若都无环,转入第1步(可能是情况1或2);

    若都有环,转入第2步(可能是情况4或5或6);

    若一个有环一个无环,直接返回NULL,因为如果他们相交,是不可能一个有环一个无环的(图中情况3);

  1.都无环的情况,退化到两个无环链表找入口点的问题(可参见<剑指offer>和leetcode:Intersection of Two Linked Lists

    1.0 先判断两条链表的长度;

    1.1 从头节点开始走,更长的链表先走"长度之差"步,然后一起走,如果相遇,则为入口点(情况2);否则无交点(情况1)

  2.都有环的情况,这种情况还要细分:

    2.0 先判断两链表环入口点是否相同,若相同,则为情况4,转入步骤2.1;若不同,则为情况5或6,转入2.2;

    2.1 如果为上图中情况4,我们可以把两链表交点作为"假想的尾部节点",然后就退化成两个无环链表找交点的问题了;

    2.2 为判断两链表是否有交点,我们可以从第一个环的入口节点的下一个节点开始next,如果遇到了第二个链表环的入口节点,则返回第一个链表的入口节点(情况5:题目说找出第一个相交的节点,其实我觉得返回第二个链表的入口节点也行);反之,若走了一圈没遇到第二个链表环的入口节点,说明两链表不相交(情况6);

  至此,程序执行结束.设计很巧妙,要熟练掌握.

文章评论

程序员的鄙视链
程序员的鄙视链
程序员和编码员之间的区别
程序员和编码员之间的区别
老程序员的下场
老程序员的下场
漫画:程序员的工作
漫画:程序员的工作
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
如何成为一名黑客
如何成为一名黑客
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
中美印日四国程序员比较
中美印日四国程序员比较
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
10个调试和排错的小建议
10个调试和排错的小建议
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
旅行,写作,编程
旅行,写作,编程
程序员都该阅读的书
程序员都该阅读的书
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员必看的十大电影
程序员必看的十大电影
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
为什么程序员都是夜猫子
为什么程序员都是夜猫子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
Java程序员必看电影
Java程序员必看电影
编程语言是女人
编程语言是女人
总结2014中国互联网十大段子
总结2014中国互联网十大段子
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
 程序员的样子
程序员的样子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
代码女神横空出世
代码女神横空出世
鲜为人知的编程真相
鲜为人知的编程真相
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有