Leetcode 160. 相交链表

àì夳堔傛蜴生んèń 2024-04-17 05:35 72阅读 0赞

> 《剑指 Offer》 [52. 两个链表的第一个公共节点][52.]

### 文章目录 ###

*  1. 辅助栈
 *   *  1.1 思路
     *  1.2 复杂度
     *  1.3 代码
 *  2. 双指针
 *   *  2.1 思路
     *  2.2 复杂度
     *  2.3 代码

# 1. 辅助栈 #

## 1.1 思路 ##

相交链表必成 `Y` 型，即头部分叉、尾部相同。因此，从尾部开始比对，直到找到最后一个相同的节点，即为链表的第一个公共节点。

利用辅助栈，将链表倒置，实现倒序比较。以空间换时间，在空间复杂度上还可以进一步优化。

## 1.2 复杂度 ##

*  时间复杂度 O(m+n)
 *  空间复杂度 O(m+n)

## 1.3 代码 ##

class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if (headA == null || headB == null) { 
                return null;
            }
            Stack<ListNode> s1 = new Stack<>();
            Stack<ListNode> s2 = new Stack<>();
            while (headA != null) { 
                s1.push(headA);
                headA = headA.next;
            }
            while (headB != null) { 
                s2.push(headB);
                headB = headB.next;
            }
            ListNode root = null;
            while (!s1.isEmpty() && !s2.isEmpty() && s1.peek() == s2.peek()) { 
                root = s1.pop();
                s2.pop();
            }
            return root;
        }
    }

# 2. 双指针 #

## 2.1 思路 ##

若两链表长度相同，从头开始逐节点比对，直到发现公共节点即可；若两链表长度不同，先消除长度差，再进行节点比对。

消除长度差的两种策略：

*  减去法：将长链表减去多出部分，使两链表长度相等，遍历直到发现公共节点；
 *  加长法：长链表尾部接上短链表，短链表尾部接上长链表，使两链表长度相等，遍历直到出现公共节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vb25zcGlyaXRhY20_size_16_color_FFFFFF_t_70]

## 2.2 复杂度 ##

*  时间复杂度 O(m+n)
 *  空间复杂度 O(1)

## 2.3 代码 ##

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if (headA == null || headB == null) { 
                return null;
            }
            ListNode curA = headA;
            ListNode curB = headB;
            while (curA != null && curB != null) { 
                curA = curA.next;
                curB = curB.next;
            }
            if (curA == null) { 
                while (curB != null) { 
                    curB = curB.next;
                    headB = headB.next;
                }
            } else { 
                while (curA != null) { 
                    curA = curA.next;
                    headA = headA.next;
                }
            }
            while (headA != null && headB != null && headA != headB) { 
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }

[52.]: https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21vb25zcGlyaXRhY20_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/06973e01c8ad42d6b498d8df3820b266.png