如果两个单链表相交，输出相交节点

秒速五厘米 2023-02-09 11:52 15阅读 0赞

### 文章目录 ###

*   *  如果两个单链表相交，输出相交节点
     *   *  一、实现
         *  二、输出

## 如果两个单链表相交，输出相交节点 ##

### 一、实现 ###

package com.mtons.mblog.leetcode;
    
    /** * 如果两个单链表相交，输出相交节点 * * 让 两个链表先处于同一起跑线，如图所示，然后再 同时向后遍历（从d和h开始同时向后遍历），那 * 么就可以确定是在哪个地方相交的了（确定了在f处相同，即交点）。 * * 那么如何让他俩处于同一起跑线呢？ * * 很简单，只需要长的链表先走 走到与短的链表一样长就可以了。 * * 所以解法： * * 1，分别计算两个链表的长度，得出差值（长的为7，短的为4，差值3） * * 2，让长的链表先走 (差值) 步，此时两个链表长度相同（长的从d开始，短的从h开始） * * 3，同时遍历两个链表，当相同时，即找到了交点。（遍历到f时相等，即交点） * * * 这里的相交不是指值一样，而是指占用同一片内存空间，完全是一样的。这点在解题的时候至关重要！！！！ * 一旦找到了一个这样的节点，那么之后两个链表的节点对应着也就占用相同的内存空间，就无需判断了。这是 * 因为由链表的性质决定的，node.next只有一个。 */
    public class NodeSame { 
    
        static class Node{ 
            int data;
            Node next;
    
            public Node(int data,Node next){ 
                this.data = data;
                this.next = next;
            }
        }
    
        public static void main(String[] args) { 
    
    
            //1->2->3->4->5
            Node node5 = new Node(5,null);
            Node node4 = new Node(4,node5);
            Node node3 = new Node(3,node4);
            Node node2 = new Node(2,node3);
            Node node1 = new Node(1,node2);
    
    
            //设置相交的Node节点是node4 即:6->4->5
            Node node6 = new Node(6,node4);
    
            Node result = getSameNode(node1,node6);
            System.out.println(result.data);
    
    
        }
    
        public static Node getSameNode(Node head1,Node head2){ 
    
            if(head1 == null || head2 == null){ 
                return null;
            }
    
            Node head1Temp = head1;
            Node head2Temp = head2;
    
            int head1Len = 0;
            int head2Len = 0;
    
            while (head1Temp != null){ 
                head1Len++;
                head1Temp = head1Temp.next;
            }
    
            while (head2Temp != null){ 
                head2Len++;
                head2Temp = head2Temp.next;
            }
    
            head1Temp = head1;
            head2Temp = head2;
    
            Node result = null;
    
            while (head1Len > head2Len){ 
                head1Temp = head1Temp.next;
                head1Len--;
            }
    
            while (head1Len < head2Len){ 
                head2Temp = head2Temp.next;
                head2Len--;
            }
    
            while (true){ 
    
                if(head1Temp == head2Temp){ 
                    result = head1Temp;
                    break;
                }
    
                //如果没有相交 那么直接跳出循环
                if(head1Temp == null || head2Temp == null){ 
                    break;
                }
    
                head1Temp = head1Temp.next;
                head2Temp = head2Temp.next;
            }
    
            return result;
        }
    }

### 二、输出 ###