链表相关算法

1.删除链表指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LinkedNode{
	public LinkedNode removeElement(LinkedNode head, int val){
		
		//先从头结点开始删
		while(head != null && head.val == val){
			head = head.next;
		}
		
		if(head==null){
			return head;
		}
		
		LinkedNode pre = head;
		while(pre.next!=null){
			if(pre.next.val==val){
				pre.next = pre.next.next;
			}else{
				pre = pre.next;
			}
		}
		return head;
	}
}

2.有序链表插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LinkedNode{
	public void insertElement(LinkedNode node){
		LinkedNode pre = null;
		LinkedNode current = first;
		while(current!=null&&node.value<current.value){
			pre = current;
			current = current.next;
		}
		
		if(pre==null){
			first = node;
		}else{
			pre.next = node;
		}
		node.next = current;
	}
}

3.判断链表是否有环，如果有找出环的入口点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode<T> isLoopList(ListNode<T> head){
	ListNode<T> slowPointer, fastPointer;
	slowPointer = fastPointer = head;
	while(fastPointer != null && fastPointer.next != null){
		slowPointer=slowPointer.next;
		fastPointer=fastPointer.next.next;
		if(slowPointer == fastPointer){
			break;
		}
	} 
	//有环
	if(fastPointer != null && fastPointer.next != null){
		while(fastPointer != head){
			fastPointer=fastPointer.next;
			head=head.next;
		}
		return fastPointer;
	}else{
		return null;
	}
}