• 两个单链表相交的问题

    两链表相交及其第一个节点 

     

    判断有环无环

    判断有无环，如果有环返回第一个入环节点，如果无环返回null

    使用额外空间：Set结构

    沿着指针将a、b、c、d、e、c放入set结构中，每次放入前查看在set集合中是否存在；

    若遍历到null都没有重复节点，那么链表为无环链表；

    若有重复，链表有环，第一个重复的值即为第一个入环节点

    不使用额外空间

    如果一个链表无环，一定能够指向null

    如果一个链表有环，最终它一定在一直循环

    快慢指针：快指针一次走两步，慢指针一次走一步

    如果一个链表无环，快指针先指向null

    如果一个链表有环，快满指针一定会在某一时刻相遇

    （不一定在入环节点相遇并且慢指针在环中转的圈数不超过两圈）

    相遇之后，慢指针在原地，快指针回到起点，接下来快慢指针都走一步，两个指针一定会在入环节点相遇（数学证明）

    1. //判断有环无环，有环返回第一个入环节点，无环返回null
    2.     public static Node getloopNode(Node head) {
    3.  
    4.         if (head == null || head.next == null || head.next.next == null) {
    5.             return null;
    6.         }
    7.  
    8.         //快慢指针相遇的时候停止，如果快慢指针都从head出发，开始时相遇，所以快指针先走两步，慢指针走一步
    9.         Node slow = head.next;
    10.         Node fast = head.next.next;
    11.         while (slow != fast) {
    12.             if (fast.next == null || fast.next.next == null) {//无环
    13.                 return null;
    14.             }
    15.  
    16.             slow = slow.next;
    17.             fast = fast.next.next;
    18.         }
    19.  
    20.         fast = head;//回到开头
    21.         while (slow != fast) {
    22.             slow = slow.next;
    23.             fast = fast.next;
    24.         }
    25.  
    26.         return slow;
    27.     }

    对两个链表分类讨论

    两个链表分别调用getloopNode方法

    两个无环单链表

            loop1 == null        loop2 == null

            不可能如左图所示，单链表只能有一个next指针；如果两链表相交，一定是右图所示

                         

          先遍历两个链表，记录两链表的长度；

          比较链表最后一个Node，如果相等，则两链表相交；若不相等，则两链表不相交

          长链表先走两个链表之间的长度差，之后两链表再一起走，两链表在第一个相交节点处相遇  

    1. //如果两个链表都无环，判断两链表是否相交，相交则返回第一个相交节点，不相交则返回null
    2.     public static Node noLoop(Node head1, Node head2) {
    3.         if (head1 == null || head2 == null) {
    4.             return null;
    5.         }
    6.  
    7.         int length1 = 0, length2 = 0;
    8.         //遍历链表1
    9.         while (head1.next != null) {//链表1在最后一个节点停
    10.             length1++;
    11.             head1 = head1.next;
    12.         }
    13.         //遍历链表2
    14.         while (head2.next != null) {//链表2在最后一个节点停
    15.             length2++;
    16.             head2 = head2.next;
    17.         }
    18.  
    19.         if (head1 == head2) {//不相交
    20.             return null;
    21.         } else {
    22.             while(head1 != head2){//还没相遇
    23.                 if (length1 > length2) {//链表1较长
    24.                     length1--;
    25.                     head1 = head1.next;
    26.                     
    27.                 } else if (length1 < length2) {//链表2较长
    28.                     length2--;
    29.                     head2 = head2.next;
    30.  
    31.                 } else {//长链表先走了差值长度之后，两链表一起走直到相遇
    32.                     head1 = head1.next;
    33.                     head2 = head2.next;
    34.                 }
    35.             }
    36.         }
    37.         
    38.         return head1;
    39.     }

    一个有环单链表，一个无环单链表 

    此种情况两链表不可能相交，一定会有某个节点有两个next指针

    两个有环单链表

                                                          

    情况2：求相交节点 = 两无环单链表求相交节点

                 把入环节点看成结尾，终止节点为loop1==loop2

    情况1和情况3：loop1继续向下走，如果在循环中没有遇到loop2，则两链表不相交；

                             如果在循环的过程中遇到了loop2，则两链表相交

                             返回的结果既可以是loop1，也可以是loop2，两个节点都是两链表的相交节点

    1. //如果两个链表都有环，判断两链表是否相交，相交则返回第一个相交节点，不相交则返回null
    2.     //loop1 = getloopNode(head1);   loop2 = getloopNode(head2);
    3.     public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
    4.  
    5.         if (loop1 == loop2) {//情况2
    6.  
    7.             int length1 = 0, length2 = 0;
    8.             //遍历链表1
    9.             while (head1.next != null) {//链表1在最后一个节点停
    10.                 length1++;
    11.                 head1 = head1.next;
    12.             }
    13.             //遍历链表2
    14.             while (head2.next != null) {//链表2在最后一个节点停
    15.                 length2++;
    16.                 head2 = head2.next;
    17.             }
    18.  
    19.             if (head1 == head2) {//不相交
    20.                 return null;
    21.             } else {
    22.                 while (head1 != head2) {//还没相遇
    23.                     if (length1 > length2) {//链表1较长
    24.                         length1--;
    25.                         head1 = head1.next;
    26.  
    27.                     } else if (length1 < length2) {//链表2较长
    28.                         length2--;
    29.                         head2 = head2.next;
    30.  
    31.                     } else {//长链表先走了差值长度之后，两链表一起走直到相遇
    32.                         head1 = head1.next;
    33.                         head2 = head2.next;
    34.                     }
    35.                 }
    36.             }
    37.             return head1;
    38.  
    39.         } else {//情况1和情况3
    40.  
    41.             Node temp = loop1.next;
    42.             while (temp != loop1) {//在圈里面遍历
    43.  
    44.                 if (temp == loop2) {//遇到loop2，情况3
    45.                     return loop1;//return loop2;
    46.                 }
    47.                 temp = temp.next;
    48.             }
    49.  
    50.             return null;//情况1
    51.         }
    52.     }

    回到题目

    调用 

    1. public static Node getIntersectNode(Node head1,Node head2){
    2.         if(head1 == null || head2 == null){
    3.             return null;
    4.         }
    5.  
    6.         Node loop1 = getloopNode(head1);
    7.         Node loop2 = getloopNode(head2);
    8.         if(loop1 == null && loop2 == null){
    9.             return noLoop(head1,head2);
    10.         } else if (loop1 != null && loop2 != null) {
    11.             return bothLoop(head1,head2,loop1,loop2);
    12.         }else{
    13.             return null;
    14.         }
    15.     }

     全代码

    1. package linkedlist;
    2.  
    3. public class IntersectLinkedList {
    4.     class Node {
    5.         public int value;
    6.         public Node next;
    7.  
    8.         public Node(int data) {
    9.             this.value = data;
    10.         }
    11.  
    12.     }
    13.  
    14.     //判断有环无环，有环返回第一个入环节点，无环返回null
    15.     public static Node getloopNode(Node head) {
    16.  
    17.         if (head == null || head.next == null || head.next.next == null) {
    18.             return null;
    19.         }
    20.  
    21.         //快慢指针相遇的时候停止，如果快慢指针都从head出发，开始时相遇，所以快指针先走两步，慢指针走一步
    22.         Node slow = head.next;
    23.         Node fast = head.next.next;
    24.         while (slow != fast) {
    25.             if (fast.next == null || fast.next.next == null) {//无环
    26.                 return null;
    27.             }
    28.  
    29.             slow = slow.next;
    30.             fast = fast.next.next;
    31.         }
    32.  
    33.         fast = head;//回到开头
    34.         while (slow != fast) {
    35.             slow = slow.next;
    36.             fast = fast.next;
    37.         }
    38.  
    39.         return slow;
    40.     }
    41.  
    42.  
    43.     //如果两个链表都无环，判断两链表是否相交，相交则返回第一个相交节点，不相交则返回null
    44.     public static Node noLoop(Node head1, Node head2) {
    45.         if (head1 == null || head2 == null) {
    46.             return null;
    47.         }
    48.  
    49.         int length1 = 0, length2 = 0;
    50.         //遍历链表1
    51.         while (head1.next != null) {//链表1在最后一个节点停
    52.             length1++;
    53.             head1 = head1.next;
    54.         }
    55.         //遍历链表2
    56.         while (head2.next != null) {//链表2在最后一个节点停
    57.             length2++;
    58.             head2 = head2.next;
    59.         }
    60.  
    61.         if (head1 == head2) {//不相交
    62.             return null;
    63.         } else {
    64.             while (head1 != head2) {//还没相遇
    65.                 if (length1 > length2) {//链表1较长
    66.                     length1--;
    67.                     head1 = head1.next;
    68.  
    69.                 } else if (length1 < length2) {//链表2较长
    70.                     length2--;
    71.                     head2 = head2.next;
    72.  
    73.                 } else {//长链表先走了差值长度之后，两链表一起走直到相遇
    74.                     head1 = head1.next;
    75.                     head2 = head2.next;
    76.                 }
    77.             }
    78.         }
    79.  
    80.         return head1;
    81.     }
    82.  
    83.  
    84.     //如果两个链表都有环，判断两链表是否相交，相交则返回第一个相交节点，不相交则返回null
    85.     //loop1 = getloopNode(head1);   loop2 = getloopNode(head2);
    86.     public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
    87.  
    88.         if (loop1 == loop2) {//情况2
    89.  
    90.             int length1 = 0, length2 = 0;
    91.             //遍历链表1
    92.             while (head1.next != null) {//链表1在最后一个节点停
    93.                 length1++;
    94.                 head1 = head1.next;
    95.             }
    96.             //遍历链表2
    97.             while (head2.next != null) {//链表2在最后一个节点停
    98.                 length2++;
    99.                 head2 = head2.next;
    100.             }
    101.  
    102.             if (head1 == head2) {//不相交
    103.                 return null;
    104.             } else {
    105.                 while (head1 != head2) {//还没相遇
    106.                     if (length1 > length2) {//链表1较长
    107.                         length1--;
    108.                         head1 = head1.next;
    109.  
    110.                     } else if (length1 < length2) {//链表2较长
    111.                         length2--;
    112.                         head2 = head2.next;
    113.  
    114.                     } else {//长链表先走了差值长度之后，两链表一起走直到相遇
    115.                         head1 = head1.next;
    116.                         head2 = head2.next;
    117.                     }
    118.                 }
    119.             }
    120.             return head1;
    121.  
    122.         } else {//情况1和情况3
    123.  
    124.             Node temp = loop1.next;
    125.             while (temp != loop1) {//在圈里面遍历
    126.  
    127.                 if (temp == loop2) {//遇到loop2，情况3
    128.                     return loop1;//return loop2;
    129.                 }
    130.                 temp = temp.next;
    131.             }
    132.         }
    133.         return null;//情况1
    134.     }
    135.  
    136.     public static Node getIntersectNode(Node head1,Node head2){
    137.         if(head1 == null || head2 == null){
    138.             return null;
    139.         }
    140.  
    141.         Node loop1 = getloopNode(head1);
    142.         Node loop2 = getloopNode(head2);
    143.         if(loop1 == null && loop2 == null){
    144.             return noLoop(head1,head2);
    145.         } else if (loop1 != null && loop2 != null) {
    146.             return bothLoop(head1,head2,loop1,loop2);
    147.         }else{
    148.             return null;
    149.         }
    150.     }
    151.     
    152.  
    153. }
    154.  
    155.  
    156.  
    157.
  • 相关阅读:
    PMP每日一练 | 考试不迷路-9.14（包含敏捷+多选）
    windows环境如何查询端口号占用及杀死进程
    小程序长文本限制显示行数
    腾讯云网站备案详细流程_审核时间说明
    配置Flutter开发环境
    线性时间选择（Top K）问题（Java）
    基于Java的4S店汽车商城系统设计与实现(源码+lw+部署文档+讲解等)
    力扣26. 删除有序数组中的重复项
    C语言练习百题之位符号|的使用
    C#使用自定义的泛型节点类 Node＜T＞实现二叉树类BinaryTree＜T＞及其方法
  • 原文地址：https://blog.csdn.net/m0_73530538/article/details/132890052