#鏈表
>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;
}
}
~~~
