专栏首页赵俊的Java专栏两个链表的交叉

两个链表的交叉

题意

请写一个程序,找到两个单链表最开始的交叉节点。

注意事项:

  • 如果两个链表没有交叉,返回 null
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。

样例

下列两个链表:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始交叉。

思路

本题不用考虑 有环链表的情况,所以较为简单。

哈希表

利用哈希表,先将 A 链表所有元素加入到哈希表中,然后遍历 B 数组,判断每一个元素是否已在哈希表中存在,如果已存在,则已存在的节点就是交叉节点。

取长度法

首先将两个链表都遍历一次,取到两个的长度,记作 m 和 n,如果两个链表有交叉,那么两个链表的最后一个节点,一定是一样的。

这里用样例中的两个链表举例, A 链表的的长度:n = 5, B 链表的长度:m = 6 ,如果两者有相交节点,那么最多也只能是从长度较少节点的头结点到未节点。所以从较长链表 B 的第 m - n 位开始,从较短节点的头节点开始,依次向后,如果两个元素相同,则说明为交叉点。

代码实现

哈希表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;      
 *     }
 * }
 */
 
     
public class Solution {
    /**
     * @param headA: the first list
     * @param headB: the second list
     * @return: a ListNode 
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        
        HashSet<ListNode> map = new HashSet<ListNode>();
        while (p1 != null) {
            map.add(p1);
            p1 = p1.next;
        }
        
        while (p2 != null) {
            if (map.contains(p2)) {
                return p2;
            }            
            p2 = p2.next;
        }
        
        return null;
    }  
}

取长度法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;      
 *     }
 * }
 */
 
     
public class Solution {
    /**
     * @param headA: the first list
     * @param headB: the second list
     * @return: a ListNode 
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        ListNode n1 = headA;
        ListNode n2 = headB;
        for (int i = 0; i < Math.abs(lenA - lenB); i++) {
            if (lenA > lenB)
                n1 = n1.next;
            else n2 = n2.next;
        }
        
        while (n1 != null && n2 != null) {
            if (n1.val == n2.val && n1.next == n2.next) {
                return n1;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        return null;
    }  
    
    public int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        int length = 0;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            length++;
        }
        return length;
    }
}

原题地址

LintCode:两个链表的交叉

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++简单实现八皇后问题

    forrestlin
  • 线性表

    Dwyane
  • Java虚拟机--运行时栈帧结构

    SuperHeroes
  • Java虚拟机--类加载过程

    SuperHeroes
  • 十年程序员老兵告诉你,2018年程序员如何发展

    本文根据作者亲身经验、体会和思考,为工作年限在10年之内的程序员,尤其是职场新人,提供了一些建议。

    技术zhai
  • 网络流算法Dinic的Python实现

    forrestlin
  • [ Java学习基础 ] Java的对象容器 -- 集合

    Kevin_Zhang
  • 问题:实际开发中的深浅拷贝问题

    小蠢驴打代码
  • Java虚拟机--内存区域划分

    SuperHeroes
  • dancing links解决X问题的C++实现

    X问题,也称精确覆盖问题,就是给定一个01矩阵,需要从中选取一些行组成一个子矩阵,这个子矩阵的每一列有且仅有一个1。这个问题听起来就知道很难,必须使...

    forrestlin

扫码关注云+社区

领取腾讯云代金券