Java教程

力扣面试题02.07(链表相交)

本文主要是介绍力扣面试题02.07(链表相交),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

面试题02.07 链表相交

1、基本思想:

根据快慢准则,走的快的一定会追上走的慢的。

这道题中,走的链表短,那么指针走完短的链表以后就去走长的链表,可以理解为走得快的指针

只要其中一个链表走完了,就去走另一条链表。如果有交点,他们一定会相遇

1、代码:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode h1 = headA, h2 = headB;
        while (h1 != h2){
            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }
        return h1;
    }
}

 

2、基本思想:看代码随想录的

(1)设两个指针指向两个链表的头节点

(2)求出两个链表的长度,并求出长度的差值,让curA移动到和curB对齐的位置

(3)比较curA和curB是否相同,不同的话在向后移动,再比较。

 

2、代码:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头,lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上(末尾位置对齐)
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB,遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
    
}

 

这篇关于力扣面试题02.07(链表相交)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!