双链表找相交结点

旧城等待， 2024-02-21 10:56 5阅读 0赞

思路：

1.  遍历两个双链表，分别求出它们的长度（节点数）。
2.  如果两个链表相交，它们在交点之后的部分长度应该是一样的。因此，可以计算出两个链表的长度差（如果有的话），并且让较长的链表先向前移动长度差个结点，使得它们处于相同的长度上。
3.  接下来，同时遍历两个链表，比较它们的结点是否相同。当找到第一个相同的结点时，即为相交结点。
4.  如果两个链表不相交，它们将在尾部同时到达 null，此时可以返回 null 表示没有相交结点。

实现上述思路：

import org.junit.jupiter.api.Test;
    import static org.junit.jupiter.api.Assertions.assertEquals;
    
    class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int val) {
        
            this.val = val;
            this.next = null;
        }
    }
    
    public class IntersectionOfTwoLinkedLists {
        
        // 查找相交结点的方法
        public ListNode findIntersection(ListNode headA, ListNode headB) {
        
            int lenA = getLength(headA);
            int lenB = getLength(headB);
    
            // 将较长链表前移，使它们处于相同长度上
            while (lenA > lenB) {
        
                headA = headA.next;
                lenA--;
            }
    
            while (lenB > lenA) {
        
                headB = headB.next;
                lenB--;
            }
    
            // 同时遍历链表，找到第一个相交结点
            while (headA != null && headB != null) {
        
                if (headA == headB) {
        
                    return headA;
                }
                headA = headA.next;
                headB = headB.next;
            }
    
            return null;
        }
    
        // 辅助方法：计算链表长度
        private int getLength(ListNode head) {
        
            int length = 0;
            while (head != null) {
        
                length++;
                head = head.next;
            }
            return length;
        }
    
        // 单元测试
        @Test
        public void testFindIntersection() {
        
            // 创建两个链表
            ListNode commonNode = new ListNode(4);
            commonNode.next = new ListNode(5);
    
            ListNode headA = new ListNode(1);
            headA.next = new ListNode(2);
            headA.next.next = commonNode;
    
            ListNode headB = new ListNode(3);
            headB.next = commonNode;
    
            IntersectionOfTwoLinkedLists solution = new IntersectionOfTwoLinkedLists();
    
            // 测试方法
            ListNode intersection = solution.findIntersection(headA, headB);
    
            // 验证结果
            assertEquals(4, intersection.val);
        }
    }