《算法通关村第一关-黄金挑战笔记》单链表的环问题，及双链表单基本操作

如果单链表中的尾节点没有指向空，而是又指向了链表中的元素，那么这就形成了环

1.解决单链表中的环问题最容易的就是使用Hash：

      首先判断Hash中是否存在该元素，如果不存在就将该元素放入HashMap或HashSet中，并移动指针。如果该元素在Hash中已经存在，那么该元素的位置就是环的入口。 

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return null;
        }
 
HashSet<ListNode> hs=new HashSet<ListNode>();
ListNode temp=head;
 
while(temp!=null){
    if(hs.contains(temp)){
        return temp;//此时temp的位置就是环入口的位置
    }else{
        hs.add(temp);
        temp=temp.next;
    }
}

        return null;
    }
}

2.如果不能用Hash的话，还有没有其它方法来解决呢？当然是有的。

      确定链表是否有环，最有效的办法就是双指针。慢指针slow(一次走一步)，快指针fast(一次走两步)，如果fast能指到null就说明没有环。否则只要有环，两个指针不断在链表中循环就一定能相遇即(fast=slow)

    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        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;
    }

3.两个指针相遇了，证明链表有环，那么怎么确定环的入口呢。

       在上述代码基础上，我们可以将一个节点留在相遇位置，然后将另一个节点放在头节点。然后让它们以相同的速度推进，那么它们一定会在环的入口相遇。

  public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null||pHead.next==null){
return null;
        }
          
ListNode fast=pHead;
ListNode slow=pHead;
  
while(fast!=null&&fast.next!=null){
    slow=slow.next;
    fast=fast.next.next;
  
if(slow==fast){//快，慢指针相遇
//将慢指针放到头节点，快指针放在相遇位置
slow=pHead;
  
//将快，慢指针以相同速度推进，直到在环的入口相遇
while(slow!=fast){
    slow=slow.next;
    fast=fast.next;
}
  
return slow;
      
}
  
}
  
        return null;
    }

双链表

双向链表顾名思义就是既可以向前，也可以向后。相比与单链表，双链表有两个指针的好处自然是移动元素更方便。它的结构可以表示为：

 节点的定义

public class DoubleNode {
	public int data; //节点的数值
	public DoubleNode prev; //记录上一个节点的位置
	public DoubleNode next; //记录下一个节点的位置
	
	public DoubleNode(int data) {
		this.data=data;
	}
	
}

 双链表的定义

public class DoublyLinkList {
	private DoubleNode head; //双链表的头节点
	private DoubleNode last; //尾节点
	private int size; //双链表的长度
	
	public void insert(int index,int data) {
		if(index<0||index>size) {
			throw new IndexOutOfBoundsException("索引超出数组范围");
		}
		
		DoubleNode insertNode=new DoubleNode(data);//创建要插入的节点
		
		if(size==0) {//链表为空
			head=last=insertNode;
		}
		else if(index==0) {//头部插入
			insertNode.next=head;
			head.prev=insertNode;
			head=insertNode;
			
		}
		else if(index==size) {//尾部插入
			last.next=insertNode;
			insertNode.prev=last;
			last=insertNode;
		}else {//中间插入
			DoubleNode pre=getIndex(index-1);//获取插入位置的上一个节点
			insertNode.next=pre.next;
			pre.next=insertNode;
			insertNode.next.prev=insertNode;
			insertNode.prev=pre;
				
		}

		size++;
		
	}
	
	public DoubleNode remove(int index) {
		if(index<0||index>=size) {//包括链表为空的情况
			throw new IndexOutOfBoundsException("索引超出数组范围");
		}
		DoubleNode removeNode=null;
		
		if(index==0) {//头部删除
			removeNode=head;
			
			if(size==1) {//链表只有一个节点
				last=null;
			}else {
					head.next.prev=null;
			}
		
			head=head.next;
			
		}else if(index==size-1) { //尾部删除
			removeNode=last;
			last.prev.next=null;
			last=last.prev;
			
		}else {//中间删除
			DoubleNode pre=getIndex(index-1);//获取要删除节点的 上一个节点
			removeNode=pre.next;
			pre.next=pre.next.next;
			pre.next.prev=pre.next.prev.prev;
		}
		
		size--;
		return removeNode;
	}
	
	
    //获取指定位置的节点
	public DoubleNode getIndex(int index) {
		if(index<0||index>=size) {
			throw new IndexOutOfBoundsException("索引超出数组范围");
		}
		
		DoubleNode temp=head;
		int i=0;
		while(temp!=null) {
			
			if(i==index) {
				break ;
			}
			i++;
			temp=temp.next;
		}
		
		return temp;
	}
	
   //从左边开始打印链表
	public void Lshow() {
		DoubleNode temp=head;
		while(temp!=null) {
		System.out.print(temp.data+"-->");
		temp=temp.next;
		}
		System.out.print("null");
		
	}
	
    //从右边开始打印链表
	public void Rshow() {
		DoubleNode temp=last;
		while(temp!=null) {
			System.out.print(temp.data+"-->");
			temp=temp.prev;
		}
		System.out.print("null");
	}
	
}