总结：如何优雅的写出链表代码？6大学习技巧

一、理解指针或引用的含义
1.含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
2.示例：
p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

二、警惕指针丢失和内存泄漏（单链表）
1.插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
正确的写法是2句代码交换顺序，即：x—>next = p—>next; p—>next = x;
2.删除节点
在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

三、利用“哨兵”简化实现难度
1.什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
2.未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：
new_node—>next = p—>next;
p—>next = new_node;
但，若向空链表中插入一个节点，则代码如下：
if(head == null){
head = new_node;
}
如果要删除节点p的后继节点，只需1行代码即可搞定：
p—>next = p—>next—>next;
但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：
if(head—>next == null){
head = null;
}
从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。
3.引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。
4.“哨兵”还有哪些应用场景？
这个知识有限，暂时想不出来呀！但总结起来，哨兵最大的作用就是简化边界条件的处理。

四、重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件：
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？

五、举例画图，辅助思考
核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

六、多写多练，没有捷径
5个常见的链表操作：
1.单链表反转
2.链表中环的检测
3.两个有序链表合并
4.删除链表倒数第n个节点
5.求链表的中间节点

哨兵可以理解为它可以减少特殊情况的判断，比如判空，比如判越界，比如减少链表插入删除中对空链表的判断，比如例子中对i越界的判断。

空与越界可以认为是小概率情况，所以代码每一次操作都走一遍判断，在大部分情况下都会是多余的。

哨兵的巧妙就是提前将这种情况去除，比如给一个哨兵结点，以及将key赋值给数组末元素，让数组遍历不用判断越界也可以因为相等停下来。

使用哨兵的指导思想应该是将小概率需要的判断先提前扼杀，比如提前给他一个值让他不为null，或者提前预设值，或者多态的时候提前给个空实现，然后在每一次操作中不必再判断以增加效率。

谢谢老师，这节课又学到了，写完留言我要去思考那几个问题了，一个都不会。。

----

文中提到，

但是，如果我们要删除链表中的最后一个结点，前面的删除代码就不 work 了。跟插入类似，我们也需要对于这种情况特殊处理。写成代码是这样子的：

if (head->next == null) {
   head = null;
}

----

感觉此处代码处理的是当链表中只有表头一个节点的删除情况，而不是"要删除链表中的最后一个结点"的情况。是不是head应该改成p?

/**
public class Node {
    public char c;
    public Node next;
    
    public Node(char c) {
        this.c = c;
    }
}
**/
    
public static Node reverse(Node head) {
        if(head == null || head.next == null) {
            return head;
        }
        
        Node prev = null;
        Node cur = head;
        Node next = head.next;
        
        while(next != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            next = cur.next;
        }
        cur.next = prev;
        return cur;
    }
    
    
    public static boolean existsCircle(Node head) {        
        Node slow = head;
        Node fast = head;    
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;        
            if(slow == fast) {
                return true;
            }
        }        
        return false;
    }
    
        public static Node merge(Node head1, Node head2) {
        
        Node guard = new Node('/');
        Node cur = guard;
        
        while(head1 != null && head2 != null) {
            if(head1.c <= head2.c) {
                while(head1 != null && head1.c <= head2.c) {
                    cur.next = head1;
                    cur = cur.next;
                    head1 = head1.next;
                    
                }
            } else {
                while(head2 != null && head1.c > head2.c) {
                    cur.next = head2;
                    cur = cur.next;
                    head2 = head2.next;
                    
                }
            }
        }
        
        if(head1 != null) {
            cur.next = head1;
        }
        if(head2 != null) {
            cur.next = head2;
        }
        
        return guard.next;
        
    }
    
    public static Node deleteLastN(Node head, int n) {
        if(n < 1 || head == null) {
            return head;
        }
        Node guard = new Node('/');
        guard.next = head;
        
        Node slow = guard;
        Node fast = guard;
        
        for(int i = 0; i < n; i++) {
            if(fast != null) {
                fast = fast.next;
            }
        }
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return guard.next;
    }
    
    public static Node getMiddle(Node head, int n) {
        Node slow = head;
        Node fast = head;
        
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }

关于练习链表的一点体会

1、 函数中需要移动链表时，最好新建一个指针来移动，以免更改原始指针位置。

2、 单链表有带头节点和不带头结点的链表之分，一般做题默认头结点是有值的。

3、 链表的内存时不连续的，一个节点占一块内存，每块内存中有一块位置（next）存放下一节点的地址（这是单链表为例）。

3、 链表中找环的思想：创建两个指针一个快指针一次走两步一个慢指针一次走一步，若相遇则有环，若先指向nullptr则无环。

4、 链表找倒数第k个节点思想：创建两个指针，第一个先走k-1步然后两个在一同走。第一个走到最后时则第二个指针指向倒数第k位置。

5、 反向链表思想：从前往后将每个节点的指针反向，即.next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。

6、 两个有序链表合并思想：这里用到递归思想。先判断是否有一个链表是空链表，是则返回两一个链表，免得指针指向不知名区域引发程序崩溃。然后每次比较两个链表的头结点，小的值做新链表的头结点，此节点的next指针指向本函数（递归开始，参数是较小值所在链表.next和另一个链表）。

但是，如果我们要删除链表中的最后一个结点，前面的删除代码就不work了。
```
if (head->next == null) {
    head = null
}
```
这里的head表示的是最后一个结点吗？

“对于带头链表，插入头结点和插入其它节点，可以统一为相同的逻辑。”这我可以理解

但即使是带头链表，删除尾结点和删除其它节点，还是不能统一代码呀。

`p->next = p->next->next;` 无论是否是带头链表，对尾结点都没有影响呀。这行代码还是不能用于尾结点的删除呀？

1.三个节点p.pre，p，p.next，将p的next指针指向p.pre，然后p.pre=p，p=p.next，p.next=p.next.next移动指针，就可以实现单链表反转。
2.最简单就是一个节点在头，一个节点一直遍历，地址相等就是环，不过好像还有一种简单的办法，快慢前进，一次就能搞定。这个老师能不能说下自己的思路，我有点想不明白。
3.建立第三个链表，每次比较a链表当前节点和b链表当前节点的大小。如果a比b小，则c的next指针指向a当前节点，c=c.next，然后a指针后移。接着继续比较a.b当前节点大小，反之则把a换成b就行了。
4.一个p节点，然后找到距离p有n个next节点的点，一起往后遍历，到pn.next为空的时候，p就是我们要求的那个地址。
5.快慢指针，一个每次前进2个节点一个每次前进1节点。前进两个节点到表尾的时候，前进一个的就是中间点。

如何写好链表代码？

1. 理解指针或引用的含义
什么是指针？指针是一个变量，该变量中存的是其它变量的地址。将普通变量赋值给指针变量，其实是把它的地址赋值给指针变量。

2. 警惕指针丢失和内存泄漏
在插入和删除结点时，要注意先持有后面的结点再操作，否者一旦后面结点的前继指针被断开，就无法再访问，导致内存泄漏。

3. 利用哨兵简化难度
链表的插入、删除操作，需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断，链表的哨兵对象是只存指针不存数据的头结点。

4. 重点留意边界条件处理
操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想，能在其它的编码中也养成考虑边界的习惯。

5. 举例画图，辅助思考
对于比较复杂的操作，可以用纸笔画一画，释放脑容量来做逻辑处理（时间换空间思想），也便于完成后的检查。

6. 多写多练，没有捷径
孰能生巧，不管是什么算法，只有经过反复的练习，才能信手拈来。


哨兵对象思想，在 iOS AutoreleasePool 中有用到，在 AutoreleasePoolPush 时添加一个哨兵对象，Pop 时将到哨兵对象之间的所有 Autorelease 对象发送 release 消息。

代码二示例返回值int是不是写成inf了哈哈哈

算法设计思路应该是
// 用来找出给定key在数组中的下标，找不到则返回-1

a是被遍历的数组
n是数组长度
key是要寻找的值

1， 判断尾节点是不是要寻找的值，是的话返回n-1，因为数组下标从0开始所以要长度-1才是下标

2， 使用哨兵变量保存尾节点

3， 把key放到尾节点，让key成为数组中最后一个值，这样做是为了下一步的遍历

4， 开始从头开始遍历数组，i为数组下标，如果找到与key相等的元素则退出遍历，否则遍历整个数组

5， 如果i是尾节点下标，说明没有找到key，如果不是则i为寻找的节点下标，返回i

6， 把哨兵变量还原赋值到数组尾节点，也就是还原数组

也就是说平时用的临时变量就是哨兵变量