两个链表的第一个公共节点（Java实现）

迷南。 2023-07-13 13:42 79阅读 0赞

## 两个链表的第一个公共节点（Java实现） ##

**思路：** 我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
这样，当它们相遇时，所指向的结点就是第一个公共结点。

package Day40;
    
    /** * @Author Zhongger * @Description 找出两个链表相交的结点 * @Date 2020.3.12 */
    public class FindCommentNode { 
        public static void main(String[] args) { 
            ListNode commentNode = new ListNode(5);
    
            ListNode headA = new ListNode(0);
            ListNode listNodeA1 = new ListNode(1);
            ListNode listNodeA2 = new ListNode(2);
            ListNode listNodeA3 = new ListNode(3);
            ListNode listNodeA4 = new ListNode(4);
            headA.next=listNodeA1;
            listNodeA1.next=listNodeA2;
            listNodeA2.next=listNodeA3;
            listNodeA3.next=listNodeA4;
            listNodeA4.next=commentNode;
    
            ListNode headB = new ListNode(0);
            ListNode listNodeB1 = new ListNode(1);
            ListNode listNodeB2 = new ListNode(3);
            headB.next=listNodeB1;
            listNodeB1.next=listNodeB2;
            listNodeB2.next=commentNode;
    
            FindCommentNode findCommentNode = new FindCommentNode();
            System.out.println(findCommentNode.getIntersectionNode(headA, headB));
    
        }
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            int length1 = getLength(headA);
            int length2 = getLength(headB);
    
            ListNode ptr1 = headA, ptr2 = headB;
            if (length1 < length2) { 
                ptr1 = headB;
                ptr2 = headA;
            }
            int count = Math.abs(length1 - length2);
    
            while (ptr1 != null && count > 0) { 
                ptr1 = ptr1.next;
                count--;
            }
            while (ptr1 != null && ptr2 != null) { 
                if (ptr1 == ptr2) { 
                    return ptr1;
                }
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }
    
            return null;
        }
    
        private int getLength(ListNode head) { 
            int count = 0;
            while (head != null) { 
                count++;
                head = head.next;
            }
    
            return count;
        }
    
    }
    class ListNode{ 
        int val;
        ListNode next;
        public ListNode(int val){ 
            this.val=val;
        }
    
        @Override
        public String toString() { 
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }

另外，我有深入理解java虚拟机第三版的电子版资源，有需要的话加微信**973593026**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230529/c4b7351ca5f24ae7bae0b0da9c8be016.png