淘先锋技术网

首页 1 2 3 4 5 6 7
public class SingleLinkedList {
	private class Node{
		private int value;
		private Node next;
		Node(int value) {
			this.value = value;
		}
	}
	
	private static Node head;
	//尾部插入
	public void insertLast(int value) {
		Node node = new Node(value);
		if(head == null) {
			head = node;
			return;
		}
		Node temp = head;
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = node;
		//head = temp;
	}
	//头部插入
	public void insertFirst(int value) {
		Node node = new Node(value);
		node.next = head;
		head = node;
	}
	
	public void print() {
		Node temp = head;
		while(temp != null) {
			System.out.println(temp.value);
			temp = temp.next;
		}
	}
	//反转
	public void reverse() {
		Node pre = null;
		Node cur = head;
		while(cur != null) {
			//temp存储cur后面的节点
			Node temp = cur.next;
			//cur的指针指向前一个节点
			cur.next = pre;
			//把当前节点复制给前一个节点
			pre = cur;
			//当前节点向后移动
			cur = temp;
		}
		head = pre;
	}
	//是否有环
	public boolean hasCycle() {
		if(head == null) {
			return false;
		}
		Node quick = head;
		Node slow = head;
		while(quick.next != null && quick.next.next != null) {
			quick = quick.next.next;
			slow = slow.next;
			if(quick == slow) {
				return true;
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		SingleLinkedList linkedList = new SingleLinkedList();
		linkedList.insertLast(0);
		linkedList.insertLast(1);
		linkedList.insertLast(2);
		linkedList.insertLast(3);
		linkedList.insertLast(4);
		//reverse();
		linkedList.print();
	}
	//反转
	public static Node reverse1(Node node) {
	    Node prev = null;
	    Node now = node;
	    while (now != null) {
	      Node next = now.next;
	      now.next = prev;
	      prev = now;
	      now = next;
	    }

	    return prev;
	  }
	//反转
	public static Node reverse3(Node node) {
	    if(node.next==null)return node;
	    Node next = node.next;
	    node.next = null;
	    Node re = reverse3(next);
	    next.next = node;
	    return re;
	  }

}