List

[caipengbo]

主要内容

目录

[caipengbo]

dummy node

头部设置哑指针 dummy node, 这样就不用在循环中每次判断头节点是否为空（边界检查问题），也就是说每个节点都有 pre 节点

[caipengbo]

指针的操作

• 链表的指针移动
• 头插和尾部插入
• 指针的删除

重要的点：

1. 遍历指针 p 的边界判断 使用p != null 或 p.next != null
2. 封尾操作，遍历完，是不是需要对尾部进行特殊操作

[caipengbo]

链表的拆分

ListNode p = head, q = head.next;
ListNode evenHead = head.next;
while (p.next != null && p.next.next != null) {
    p.next = p.next.next;
    q.next = q.next.next;
    p = p.next;
    q = p.next;
}
p.next = null;

[caipengbo]

快慢指针

• 判断是否有环
• 判断环的第一个入口地址
• 判断相交节点的第一个交叉点

[caipengbo]

Merge

链表的归并（递归写法）