概要

鏈表（Linked List）是數據結構中的一種，用于存儲具有線性關系的數據。在鏈表中，每個元素稱為一個節點（Node），每個節點包含兩個部分：一個是數據域（存儲數據），另一個是指針域（指向下一個節點）。鏈表的結構使得它在某些情況下比數組更加高效，特別是在插入和刪除操作上。

鏈表的類型

1. 單向鏈表（Singly Linked List）：

   • 每個節點只有一個指向下一個節點的指針。
   • 頭節點（Head）是鏈表的起點，尾節點（Tail）指向 null。

2. 雙向鏈表（Doubly Linked List）：

   • 每個節點有兩個指針，分別指向前一個節點和下一個節點。
   • 頭節點的前指針和尾節點的后指針都指向 null。

3. 循環鏈表（Circular Linked List）：

   • 單向鏈表或雙向鏈表的變種。
   • 尾節點的下一個指針指向頭節點，形成一個循環。

題目：相交鏈表

原題鏈接：相交鏈表

題解

核心：其實就是讓2個指針走一樣的距離，消除步行差，那就一定可以一起走到相交點

因為兩個鏈表如果相交，則它們從相交點到結尾的所有節點都是相同的。因此，我們讓指針 p1 和 p2 分別遍歷兩個鏈表。如果 p1 到達鏈表 A 的末尾，則將其重定位到鏈表 B 的頭部；同樣地，如果 p2 到達鏈表 B 的末尾，則將其重定位到鏈表 A 的頭部。這樣，兩指針最終會在相交點處相遇，即第一個共同節點，即為相交點。

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA;ListNode p2 = headB;while (p1 != p2) {p1 = p1 == null ? headB : p1.next;p2 = p2 == null ? headA : p2.next;}return p1;}

評論區看到一個【還有句話：走到盡頭見不到你，于是走過你來時的路，等到相遇時才發現，你也走過我來時的路。】

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode she = headA;ListNode he = headB;// 直到兩人相遇while (she != he) {if (she != null) {she = she.next;// 如果她沒走到盡頭就一直走下去} else {she = headB;// 直到盡頭也沒遇見他，所以她去往他走過的路}if (he != null) {he = he.next;} else {he = headA;}}return he;// 返回兩人第一次相遇的地方}