Java 单链表的几个功能实现 -2-篇

练习：给定一个链表，但不知道链表大小，要求只遍历一遍，找到链表的中间位置。

 快慢指针法：

快指针指向 null 时，那慢指针指向的就是中间位置。

public Node findMid() {
		//定义fast
		Node fast =head;
		//定义slow
		Node slow=head;
		while((fast!=null)&&(fast.next!=null)){
			fast=fast.next.next;
			slow=slow.next;
		}
		return slow;
	}

判断一个链表是否有环：

快慢指针法

快（动一次移2个） 慢（动一次移1个） 指针 都从开头移动 ，能相遇 那就成环

	public boolean HashCycle() {
		//定义fast
		Node fast =head;
		//定义slow
		Node slow=head;
		while((fast!=null)&&(fast.next!=null)){
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow) {
				return true;
			}
		}
		return false;
	}

判断成环的位置

 让一个指针重新指向开头，另一个指针指向第一次相遇位置，同样速度移动，再次相遇时就是成环位置。

public void HashCycle1(){
		//定义fast
		Node fast =head;
		//定义slow
		Node slow=head;
		while((fast!=null)&&(fast.next!=null)){
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow) {
				while(slow!=fast) {
					fast=fast.next;
					slow=slow.next;
				}
				System.out.println(slow.val);
				return ;
			}
		}

	}

实现链表反转 不新建内存空间

1个指向head（头）节点的前一个位置

1个指向head（头）的后一个节点位置

//链表翻转
	public void fanzhuan() {
		Node pre=null;
		Node next=null;
		while(head!=null) {
			next=head.next;
			head.next=pre;
			pre=head;
			head=next;
		}
		head=pre;
	}

截取单链表后k个节点

	//截取单链表的后k个节点
	public void NthFromEnd(int k) {
		Node fast=head;
		Node slow=head;
		while((fast!=null)&& k>=1){
			fast = fast.next;
			k--;
		}
		while(fast != null) {
			fast = fast.next;
			slow = slow.next;
		}
		head = slow;

	}