Java实现LeetCode题目（链表）

Leetcode203去除链表元素

package link_list;
public class removePoint {
	//无虚拟结点的方法,注意不能操作空指针
	public static ListNode removeElement(ListNode head,int target) {
		while(head!=null&&head.val==target) { //判断头结点是不是为空 为什么是while[1,1,1,1]
			head = head.next;
		}
		ListNode cur = head;
		while(cur!=null&&cur.next!=null) {
			if(cur.next.val==target) {
				cur.next=cur.next.next;
			}else {
				cur = cur.next;
			}
		}
		return head;
	}
	
	//虚拟结点
	public static ListNode removeElement2(ListNode head,int target) {
		if(head==null) {
			return head;
		}
		ListNode demmyHead = new ListNode(-1,head);
		ListNode cur = demmyHead;
		while(cur.next!=null) {
			if(cur.next.val==target) {
				cur.next=cur.next.next;
			}else {
				cur=cur.next;
			}
		}
		head = demmyHead.next;
		return head;
		
		
	}

}

Leetcode707设计链表

使用Java设计一个链表

package link_list;



public class Design_Link {
	public static void main(String[] args) {
		Design_Link demo = new Design_Link();
		
		Design_Link.myLinkedList myLink = new Design_Link().new myLinkedList();
		myLink.addHead(0);
		myLink.addIndex(1,1);
		myLink.addTail(2);
		myLink.addTail(2);
		myLink.printVal();
		myLink.get(1);
		
	}
	class ListNode{
		int val;
		ListNode next;
		public ListNode() {
			
		}
		public ListNode(int val) {
			this.val=val;
		}
		public ListNode(int val,ListNode linkNode) {
			this.val=val;
			this.next = linkNode;
		}
	}
	class myLinkedList{
		//记录链表大小
		int size;
		//虚拟头结点
		ListNode head;
		public myLinkedList(){
			size = 0;
			head = new ListNode(0,null); 
		}
		//获取第index个结点的数值，注意index是从0开始的，第0个结点就是头结点。
		public void get(int index) {
			if(index<0||index>=size) {
				System.out.print("格式错误");
			}
			ListNode cur = head;
			//包含虚拟结点，所以查找第index+1个结点
			for(int i =0;i<=index;i++) {
				cur = cur.next;
			}
			System.out.println(cur.val);		
		}
		// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
	    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
	    // 如果 index 大于链表的长度，则返回空
		public void addIndex(int index,int val) {
			if(index<0) {
				index = 0;
			}else if(index>size) {
				return;
			}
			size++;
			//找到要插入的结点前驱动
			ListNode pred = head;
			for(int i =0;i<index;i++) {
				pred = pred.next;
			}
			ListNode curAdd = new ListNode(val);
			curAdd.next = pred.next;
			pred.next= curAdd;
		}
		//插入最前面的节点，等价于在第0个元素添加
		public void addHead(int val) {
			addIndex(0,val);
		}
		//最后插入
		public void addTail(int val) {
			addIndex(size,val);
		}
		
		//删除第index个元素
		public void deleteIndex(int index) {
			if(index <0||index>=size) {
				return;
			}
			size--;
			ListNode pred = head;
			for(int i =0;i<index;i++) {
				pred = pred.next;
			}
			pred.next = pred.next.next;
		}
		public void printVal() {
			ListNode cur = head.next;
			if(cur!=null) {
				for(int i=0;i<size;i++) {
					System.out.print(cur.val+"\t");
					cur = cur.next;
				}
			}else {
				System.out.println("链表为空");
			}
			
		}
	}
}

LeetCode206反转链表

package link_list;
public class Revert_Link {
	public ListNode revertLink(ListNode head) {
		ListNode pre = new ListNode();
		ListNode cur = head.next;
		ListNode temp = new ListNode();
		while(temp!=null){
			temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur=temp;
		}
		return pre;
	}
}

Leetcode19删除链表倒数第n个元素

package link_list;

public class Remove_Last {
	public ListNode  removeNthFromEnd(ListNode head,int n) {
		ListNode demmyHead = new ListNode(0);
		demmyHead.next=head;
		ListNode fast = demmyHead;
		ListNode slow = demmyHead;
		for(int i=0;i<=n;i++) {
			fast = fast.next;
		}
		while(fast!=null) {
			fast = fast.next;
			slow =slow.next;
		}
		slow.next = slow.next.next;
		return demmyHead.next;
	}
}

Leetcode160链表相交

package link_list;

public final class Link_Intersection {
	 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		 	//指针相等
			ListNode curA = headA;
			ListNode curB = headB;
			int lenA = 0;
			int lenB = 0;
			while(curA.next!=null) {
				lenA++;
				curA = curA.next; 
			}
			while(curB.next!=null) {
				lenB++;
				curB = curB.next;
			}
			curA=headA;
			curB=headB;
			//让curA指向最长的链表
			if(lenB>lenA) {
				int lenTemp = lenA;
				lenA = lenB;
				lenB = lenTemp;
				
				ListNode tempNode = curA;
				curA = curB;
				curB =tempNode;
			}
			int gap = lenA-lenB;
			while(gap--!=0) {
				curA = curA.next;
			}
			while(curA!=null){
				if(curA==curB) {
					return curA;
				}else {
					curA = curA.next;
					curB = curB.next;
				}
			}
			return null;

	    }
}

Leetcode 142环形链表II

package link_list;

public class Loop_Link {
	public ListNode findWay(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;//有环的话快慢指针必定相遇
		//两个数一个环的情况得到循环条件，
		while(fast!=null&&fast.next!=null) {
			fast = fast.next.next;
			slow = slow.next;
			if(fast == slow) {
				ListNode index1 = head;
				ListNode index2 = fast;
				while(index1!=index2) {
					index1=index1.next;
					index2=index2.next;
				}
				return index2;
			}
		}
		return null;
	}
}