#链表
>1.有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。
给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。
测试样例：
[1,3,4,5,7],[1,2,3,4,0],2
返回：{1,2,3,4,5,7}
~~~
import java.util.*;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class InsertValue {
public ListNode insert(int[] A, int[] nxt, int val) {
if(A==null||A.length==0){
return new ListNode(val);
}
ListNode head = new ListNode(A[0]);
ListNode p = head;
for(int i=0;i<A.length-1;i++){
p.next = new ListNode(A[nxt[i]]);
p = p.next;
}
p.next=null;//p.next=head变成环OJ上过不了。
ListNode pre = head;
ListNode next = head.next;
ListNode newNode = new ListNode(val);
while(next!=null){
if(val>=pre.val&&val<=next.val){
break;
}
pre = next;
next = next.next;
}
newNode.next = next;
pre.next = newNode;
if(val<head.val){
return newNode;
}else{
return head;
}
}
}
~~~
>2.现有两个升序链表，且链表中均无重复元素。请设计一个高效的算法，打印两个链表的公共值部分。
给定两个链表的头指针headA和headB，请返回一个vector，元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值
测试样例：
{1,2,3,4,5,6,7},{2,4,6,8,10}
返回：[2.4.6
~~~
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Common {
public int[] findCommonParts(ListNode head1, ListNode head2) {
LinkedList<Integer> list = new LinkedList<Integer>();
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
head1 = head1.next;
} else if (head1.val > head2.val) {
head2 = head2.next;
} else {
list.add(head1.val);
head1 = head1.next;
head2 = head2.next;
}
}
int[] res = new int[list.size()];
int index = 0;
while (!list.isEmpty()) {
res[index++] = list.pollFirst();
}
return res;
}
}
~~~
>3.现在有一个单链表。链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。
给定一个单链表的头结点head，同时给定一个值val，请返回清除后的链表的头结点，保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。
测试样例：
{1,2,3,4,3,2,1},2
{1,3,4,3,1}
~~~
import java.util.*;
public class ClearValue {
public ListNode clear(ListNode head, int val) {
// write code here
if(head==null)
return null;
ListNode p=head.next;//先不判断头结点
ListNode pre=head;
while(p!=null){
if(p.val==val){
pre.next=p.next;
}else{
pre=pre.next;
}
p=p.next;
}
if(head.val==val)
return head.next;
else
return head;
}
}
~~~
>4.如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。
给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。
~~~
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class ChkLoop {
public int chkLoop(ListNode head, int adjust) {
//判空、有、没有
//思路：两个指针从头开始一快（2步）一慢（1步）,若最后可以相聚，则链表有环
if(head==null) return -1;
ListNode slow = head;
ListNode fast = head;
do{
if( (fast==null) || (fast.next==null)){
return -1;
}
fast = fast.next.next;
slow = slow.next;
}while(slow != fast);
slow=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow.val;
}
}
~~~
