相交链表

编写一个程序,找到两个单链表相交的起始节点。

例如,下面的两个链表:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
在节点 c1 开始相交。

注意:

如果两个链表没有交点,返回 null.

在返回结果后,两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        
        ListNode TempA = headA;
        ListNode TempB = headB;
        int lenA = 0;
        int lenB = 0;
        
        //计算链表1的长度
        while(TempA != null)
        {
            lenA++;
            TempA = TempA.next;
        }
        
        //计算链表二的长度
        while(TempB != null)
        {
            lenB++;
            TempB = TempB.next;
        }
        
        TempA = headA;
        TempB = headB;
        //使他们起始到结束的长度相等
        if(lenA > lenB)
        {
            for(int i = 0;i<lenA - lenB;i++)
            {
                TempA = TempA.next;
            }
        }
        else
        {
            for(int i = 0;i<lenB - lenA;i++)
            {
                TempB = TempB.next;
            }
        }
        
        while(TempA != TempB)
        {
            TempA = TempA.next;
            TempB = TempB.next;
        }
        
        return TempA;
    }
}

首页 我的博客
粤ICP备17103704号