8. 相交链表

160. 相交链表 - 力扣（Leetcode）

8.1 代码实现

节点类型跟之前的一样~

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

8.2 深度解析 + 动图分析

一开始想到的方法就是，遍历N2次，即一个链表，每一个节点都在另一条链表上（整趟）找

很笨~

相交单链表的特点就是，交点到链尾，两个表是完全重合的，也就是说，两条相交的单链表，个数上的差异取决于节点之前的个数差异~

当然也可以用两次遍历确认两条的长度，然后让他们前半段的个数差抵消~

但是我不喜欢多遍历一次去测长度~

且看看我的方法~

是相交链表：

不是相交链表：

这样都指向null的时候，就会返回null

不相交返回空~

9. 循环链表之判断是否带环

141. 环形链表 - 力扣（Leetcode）

9.1 代码实现

节点类型跟之前的一样~

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {       
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

9.2 深度解析 + 动图分析

这里结合了 “快慢指针” 的性质

让两个指针速度不一样，当进入循环链表的时候

由于速度不一样，两个指针会相遇~

如果不是循环链表，快指针会很快指向null~

为什么“快慢指针”的速度为2:1？

因为其他比例，例如3:1 ，可能会导致循环链表，两个引用一直没相遇，反复错过，绕多了很多圈~

如果结尾出现，两个节点的循环，并且slow在前，fast在后~

就会出现死循环~

对于第十问，2:1 有很大的帮助！

10. 循环链表之入口点

142. 环形链表 II - 力扣（Leetcode）

10.1 代码实现

节点类型跟前面一模一样~

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        while(fast != null && fast.next != null) {       
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                while(cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return slow;
            }
        }        
          return null;
    }
}

10.2 深度解析 + 动图分析

只需要在第九题的基础上，做一些更改~

作为返回值，如果不是循环链表返回null

如果是循环链表，返回入口点，那么入口点的计算算法是什么呢？

在第九题的基础上，我们找到了相遇点，而相遇点不一定是入口点~

所以两个指针必须同时走，一快一慢~

对于相遇点有这么一个性质：相遇点与链表头节点，两个引用这两个点出发，速度为1的情况下，会在入口点相遇~

下面看我证明：

得到这个结论，因为我是按单位长度来算的，所以，只要是循环链表，就满足这个公式~

无非就是有些量为0的特殊情况~

这也是为什么用两倍的关系，这样才有这么好的性质~

这就是这一段代码的由来~

差不多就这样：

11. 补充知识点~

LinkedList有一个和顺序表一样的构造方法，可以提供一个集合类，完成拷贝~

链表知识点题库 - 力扣（LeetCode）

牛客网在线编程_编程学习|练习题_数据结构|系统设计题库 (nowcoder.com)

学会自主学习~

你现在有能力刷题了哦~

11.1 LinkedList链表的反向遍历~

对于单链表，逆序打印开销实在太大了~

所以可以借助迭代器（了解）

ListIterator是List受重写后的一个方法，listIterator(int index)

index为迭代器内部的引用，指向的是index下标~

这个迭代器既可以顺序打印，也可以逆序打印~

逆序的话，用listIterator.hasPrevious()为条件，内置引用前有元素，即可打印

listIterator.previous()为内置引用的元素

并且调用一次，引用往前走一步

    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        list.add(55);
        list.add(56);
        list.add(57);
        list.add(58);
        list.add(59);
        ListIterator<Integer> listIterator = list.listIterator(list.size());
        while(listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + " ");
        }
    }

结果正常~

11.2 ArrayList 与 LinkedList的区别

不同点 ArrayList LinkedList

存储空间空间分布紧密连续逻辑上连续，但是空间分布分散

随机访问 O(1) O(N)

头插需要挪动元素，O( N ) O(1)

插入空间不够需扩容无容量概念

应用场景元素高效存储 + 访问次数多频繁插入，频繁删除

11.3 链表归并排序（知识扩展）【涉及排序原理】

时间复杂度O(N * log2N), 空间复杂度O( 1 )；

思路跟刚才归并怎么排一致，重点在于用快慢指针找到中点，节省速度

是可以先求长度然后一直用的（就是算一次长度，然后每次都用这个长度为基准，去找mid）

之后不断合并有序链表。

看几次动图：

递归的重点就分清“整体感”，比如说下面的，我们就看做左右边已经弄好了，只要满足小问题（递归出口

），通过数学归纳法就能知道成立

ListNode left = sortList(head);
    ListNode right = sortList(tmp);

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        //避免当剩余两个节点时，中间节点变成右边那个，这样会死递归！
        //（打断链表更没有意义，右边链表是null，没用）
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null; //打断链表

技巧1：平分链表（快慢指针在Java中应该是引用，或者下标）

快慢指针，慢指针应该走到中间偏前的一个位置【不然会死递归】

以两个节点为例子，快指针走两步，慢指针走一步，然后slow.next = null不就等于没有意义吗，进入递归后，（左侧）依旧是两个节点，以此造成栈溢出！

解决方法：fast先走一步，最终slow停在中节点偏前

fast不先走一步，最终slow停在中节点偏后

        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode ret = new ListNode(0);
        //临时头节点，最终不要即可，因为我们不能确定头结点是否是谁的
        ListNode cur = ret;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                cur.next = left;
                left = left.next;
            }else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left != null ? left : right;
        return ret.next;
    }

技巧2：给需要构造的链表提供一个起始节点，（就像珍珠需要有一个小石子，最终才能积累成珠）

ListNode ret = new ListNode(0);这一句代码，提供一个带头链表

目的是因为，我们不知道首节点是谁，毕竟尾入法在首节点需要判断

那我们不如直接给一个，最终不考虑进去就行了

技巧3：合并有序链表，不用多说

【JavaOj】链表十连问