Leetcode160.相交链表

1.题目描述

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

如下面的两个链表**:**

img

在节点 c1 开始相交。

示例 1:

img

2.解答

首先我想到的方法就是将第一个链表遍历过的节点做一个标记flag,当第二个链表遍历时,如果遇到标记,那么第一个标记就是第一个交叉点,但是因为标记并不是节点本身的属性,所以这个我不知道怎么实现

下面这种解法是首先求出二者的长度的差值,让长的先走出这一段差值,然后二者手挽手,肩并肩的一起往前走,如果有相交节点,那么当两个节点满足(p1 == p2)时返回即可,如果没有相交节点,那么最后(p1 == p2)== null,返回null即可

这道题我暴露出来的问题就是对== 和equals缺乏一个深入的理解,之前一直以为自己这里会了,但是发现印象笔记上面没有笔记,博客上面也从来没有总结过,一会就着手去做,出现问题是好事,这是做题的目的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)   return null;
        int lenA = 0,lenB = 0;
        //分别遍历两个链表,求出二者长度的差值
        ListNode temp = headA;
        while(temp != null){
            lenA++;
            temp = temp.next;
        }
        temp = headB;
        while(temp != null){
            lenB++;
            temp = temp.next;
        }
        //设置变量,尽量不要移动头指针
        ListNode p1 = headA,p2 = headB;
        int diff = lenA - lenB;
        //让比较长的链表先走出差值
        while(true){
            if(diff > 0){
                p1 = p1.next;
                diff--;
            }
            if(diff < 0){
                p2 = p2.next;
                diff++;
            }
            if(diff == 0)
                break;
        }
        //当两个节点满足 == 时,返回
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

接下来是中方法我觉得脑洞比较大,而且很有想象力,非常潇洒的一种解法,

  • 两个链表都从第一个节点,每次以相同的速度向后面遍历,
  • 这样比较短的链表会先到达末尾,假如A链表比较短,那么这时让A末尾的指针指向headB,继续向后遍历,
  • 当较长的B指针到达B链表的末尾之后,让B指针指向headA,继续向后遍历,
  • 如果最终两个链表存在相交的话,那么从第一个相交节点开始,两个链表一定是手挽手,肩并肩的一起往后面走的,返回第一个即可,
  • 如果不相交,那么两个指针从头到尾,以相同的速度,走了同样远的路程,最后同时为null,返回null即可

今后写思路分析的时候通通采用这样分条的方法,不然一大段文字,自己再看的时候都头疼

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)  return null;
        ListNode p1 = headA,p2 = headB;
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

不仅思路潇洒,代码写的也是这样清新脱俗~~~


第三种方法使用了HashMap,总觉得使用这种数据结构做算法题目是一种很无赖的方法,在刷剑指offer的时候,很多练习的算法的题目都被我这样无赖过去了,有点过意不去,但是官网上面的答案里面该用还是用,我也用,莫得办法

  • 创建一个HashMap,键为节点的值,值为节点new HashMap<Integer,ListNode>()

  • 将任意一个链表中的节点全部存入HashMap中

  • 遍历另外一个链表,将每个节点和HashMap进行比较,如果HashMap中包含与当前节点Key相等的节点,那么再比较两个节点时候地址相等,也就是进行==比较

  • 进行上述两次比较之后,这样就可以确保两个节点是同一个

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<Integer,ListNode> map = new HashMap<Integer,ListNode>();
        ListNode p1 = headA;
        while(p1 != null){
            map.put(p1.val,p1);
            p1 = p1.next;
        }
        ListNode p2 = headB;
        while(p2 != null){
            if(map.containsKey(p2.val) && map.get(p2.val) == p2)
                return map.get(p2.val);
            p2 = p2.next;                            
        }
        return null;
    }
}

这种方法完成了上面我的心愿,就是将遍历过的节点做一个标记