【LeetCode】160. 相交链表

in #programming26 days ago

1 题目描述

160. 相交链表要求给定两个单链表的头节点 headAheadB,任务是找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

2 解题思路

为了解决这个问题,我们可以采用以下策略:

  1. 计算两个链表的长度:首先分别遍历两个链表以获取它们的长度。
  2. 使较长链表的头指针与较短链表的头指针对齐:如果一个链表比另一个长,我们需要让较长链表的头指针先向前移动长度差步,使得两个链表的指针处于同一位置。
  3. 同步移动两个指针直至相交:当两个链表的指针位于同一位置时,我们同步移动这两个指针。一旦两个指针相遇,即找到了相交节点。

3 Java 代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        
        // 求链表A的长度
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        
        // 求链表B的长度
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        
        curA = headA;
        curB = headB;
        
        // 让curA为最长链表的头,lenA为其长度
        if (lenB > lenA) {
            // 交换 lenA 和 lenB
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 交换 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;
    }
}
  • 时间复杂度: O(L1 + L2),其中 L1 和 L2 分别是链表 A 和链表 B 的长度。我们需要遍历每个链表一次来计算长度,然后再遍历一次以找到相交节点。
  • 空间复杂度: O(1),因为我们只使用了几个指针变量。

4 注意事项

  • 计算长度:先计算两个链表的长度,以便知道哪个链表更长。
  • 对齐起点:让较长的链表先走长度差步,使得两个链表的末尾对齐。
  • 同步遍历:然后同步遍历两个链表,直到找到相同的节点或到达链表末尾。
  • 返回结果:如果找到相交节点,返回该节点;否则返回 null

Coin Marketplace

STEEM 0.21
TRX 0.20
JST 0.034
BTC 98833.06
ETH 3391.57
USDT 1.00
SBD 3.08