算法-链表-1

哈希表(o1)

常数操作

如果存储的基本数据类型,存储的是值

如果存储的是引用类型,存储的是引用内存地址

有序表(o logn)

key有序组织

判断一个链表有环无环,第一个入环点?

快慢指针是否相交

有环判断单链表相交点?

慢指针从相交点开始快指针从头开始每次都只一步,相交的点是第一个入环点

 1 public ListNode detectCycle(ListNode head) {
 2         ListNode p1 = head;
 3         ListNode p2 = head;
 4         while (p2 != null && p2.next != null) {
 5             p1 = p1.next;
 6             p2 = p2.next.next;
 7             if (p1 == p2) {
 8                 break;
 9             }
10         }
11         if (p2 == null || p2.next == null) {
12             return null;
13         }
14         p2 = head;
15         while (p1 != p2) {
16             p1 = p1.next;
17             p2 = p2.next;
18         }
19         return p1;
20     }

无环判断双链表相交点?

长链表先走两个链表长度的差值,然后同步走相交点是相交点

两个链表的最后一个节点相等说明两个无环链表相交

一个有环一个无环不可能

两个链表都有环如何判断是否相交/相交点?

有三种情况

先求两个链表的相交点

如果两个相交点内存地址一样说明是第二种情况 ,求相交点根据无环链表规则求相交点为终点

如果一个链表遍历的过程中,能遇到第另一个相交点属于第三种情况在第一个链表遍历中遇到第二个相交点的时候是两个链表的相交点

两个相交点不相遇也不相同无相交