チェーンテーブル関連アクション

1.指定されたノードを削除し、時間複雑度O(1)

質問の説明:チェーンテーブルで指定したノードを削除します.チェーンテーブルは次のとおりです.
1->2->3->4>5;
3番目のノードを削除:
1->2->4->5;
問題の分析:
指定した位置のノードを削除し、時間の複雑さがO(1)を超えないようにし、指定したノードの次のノードの値を指定したノードの値を上書きし、指定したノードのnextをそのnextのnextに向ける.
コード実装:
ノード実装:

public class List {
	public int value;
	public List next=null;
	public List(int value)
	{
		this.value = value;
		this.next =null;
	}
	
}

チェーンテーブルを作成するには

public static List ListCreat(String list) {
	list.trim();
	if(list.length()==0)
		return null;
	String[] value =list.split(",");
	String item = value[0]; 
	List phead = new List(Integer.parseInt(item));
	List p = phead;
	for(int i = 1;i < value.length;i++){
		List q = new List(Integer.parseInt(value[i]));
		p.next = q;
		p = p.next;
	}
	return phead;
}

削除アクション:

public static void delete(int i,List head)//    
{
	List p = head;
	for(int j=1;j

2.チェーンテーブル逆置き

問題の説明:
チェーンテーブルをその場で逆置きする
問題の分析:
3つのポインタを定義します.1つはヘッダポインタheadで、1つのポインタqはnullを指し、もう1つのポインタpはヘッダポインタの次のノードを指します.qポインタが最初にnullを指すのは、後続の操作を容易にするためです.操作中にチェーンテーブルの位置情報を失わないでください.
コード実装:

public static List inverion(List head) {//     
	List q = null;
	List p = head.next;
	head.next = q;
	while(p!=null) {
		q = p;
		p = p.next;
		q.next = head;
		head = q;
	}
	return head;
}

3.返信チェーンテーブルであるか否かを判断する

問題の分析:
スタックのストレージ構造を利用して実現できます.スタックのノードのvalueがループチェーンテーブルの値に1つ1つ対応しているかどうかを判断する.
コード実装:

public static void Palindrome(List head) {//    
	Stack stack = new Stack();
	List p = head;
	while(p!=null) {
		stack.push(p);
		p = p.next;
	}
	int flag = 0;
	List t = head;
	while(t!=null) {
		List q  = stack.pop();
		if(q.value!=t.value) {
			 flag = 1;
		}
		t = t.next;
	}
	if(flag == 1)
	{
		System.out.println("NO");
	}else {
		System.out.println("Yes");
	}	
}

4チェーンテーブルにリングがあるかどうかを判断する

問題の分析:
2つのポインタを定義し、1つのポインタp 1のステップ長は2であり、もう1つのp 2のステップ長は1であり、チェーンテーブルにループが存在する場合、2つのポインタは必ず出会う.出会ったときにループを終了し、ループが存在しなければループ終了の条件はp 1またはp 2が空のときである.
コード実装:

public static void Circle(List head) {
	List p1 = head;
	List p2 = head;
	int flag = 0;
	while(p1!=null&&p2!=null) {
		p1 = p1.next;
		p2 = p2.next.next;
		if(p1==p2) {
			flag = 1;
			System.out.println("YES");
			break;
		}
	}
	if(flag==0)
	System.out.println("NO");
}