链表

1、找出链表中环的入口结点
思路1：用map记录走过的节点，当 当前节点是走过的，则为入口
思路2：快慢指针

设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。---找相遇点
接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。---分别从相遇点和链表头出发

import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode q=pHead;
        ListNode s=pHead;
        while(q!=null&&q.next!=null){
            //放前面，因为q、s初始是一样的,而环不可能只有一个节点，放弃对第一个节点的环判断
            q=q.next.next;
            s=s.next;
            if(q==s){//有相遇点q，即有环
               q=pHead;
               while(q!=s){
                   q=q.next;
                   s=s.next;
               }//此时q==s,再次相遇于入环点
               return q;
            }
        }
        return null;
    }
}

2、删除链表中重复的结点
删除链表节点时，一定要保留 前一个节点 和 最未被删除的节点/其下一个。
所以要有两个指针，一个指向被判断节点的前一个（l），一个指向被判断节点的下一个(r)。
由于第一个节点也可能被删除，所以要在最前面建立一个空白节点，作为l。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        //头尾指针
        if(pHead==null) return null;
        ListNode h=new ListNode(0);
        h.next=pHead;
        ListNode l=h;//l是目标节点的前一个
        ListNode r=null;
        while(l.next!=null&&l.next.next!=null){
            r=l.next.next;
            if(r.val==l.next.val){
                while(r!=null&&r.val==l.next.val){
                    r=r.next;
                }//r到了连续相同中的最后一个节点
                l.next=r;//现在被比较的是 连续相同中的后一个
            }
            else
                l=l.next;
        }
        return h.next;
    }
}