Javaきっときっとチェーンテーブルの各种のチェーンテーブルの面接问题、あなたは本当にすることができますか
43919 ワード
Java実装チェーンテーブル実現機能 大男たちは点噴orzを見てひざまずいた 実装機能チェーンテーブル無秩序加入データ すべてのノード情報 を印刷する.整列挿入ノード ノードデータ を修正する.削除ノード チェーンテーブル有効ノード数 を取得する.逆数K番目のノードを取得する(構想:2つのポインタ変数を定義して最初にヘッダノードを指し、最初のfirstをk-1ステップ先に行かせ、その後、2番目のsecondを最初と一緒に歩き、最初の先頭に着いた後、出力2番目が逆数K番目の要素である) チェーンテーブル をスタックで反転するヘッドプラグ法によりチェーンテーブル を反転する.は、2つの秩序化されたチェーンテーブルを統合する(非再帰的) 再帰連結チェーンテーブル コメントを見ると、面接の問題もチェーンテーブルも基本的に実現しています.
奴らはスプレーを見てひざまずいた
package DataStructure.LinkListDemo;
import java.util.Stack;
// node
class Node{
public int no;
public String name;
public Node next; //
public Node(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
//
class LinkedListDemo{
private Node head=new Node(-1,"");//
/**
*
* @param node
*/
public void add(Node node){
Node temp=head; // head, temp
while(true){
if(temp.next==null){ // ,
break;
}
temp=temp.next; // ,
}
temp.next=node; //
}
/**
*
*/
public void prtList(){
if(head.next==null) System.out.println(" ");
Node temp=head.next; // head, temp
while(true){
if(temp==null){ //
break;
}
System.out.println(temp);//
temp=temp.next;//
}
}
/**
*
*/
public void addOrder(Node node){
Node temp=head;
boolean flag=false; //
while (true){ //
if(temp.next==null){ //
break;
}
if(node.no<temp.next.no){ // temp node , temp , temp
break; //
}else if(temp.next.no==node.no){
flag=true;
break; //
}
temp=temp.next; //
}
if(flag) System.out.println(" : "+node);
else {
node.next=temp.next;
temp.next=node;
}
}
/**
*
* @param node
*/
public void updateNode(Node node){
if(head.next==null) System.out.println(" , ");
Node temp=head.next;
boolean flag=false;//
while (true){
if(temp==null) break; //
if(temp.no==node.no){
flag=true;//
break;
}
temp=temp.next;//
}
if(flag) {
temp.name=node.name;
}else{
System.out.println(" :"+node);
}
}
/**
*
* @param node
*/
public void deleteNode(Node node){
if(head.next==null) System.out.println(" , ");
Node temp=head; // head ,
boolean flag=false;//
while(true){
if(temp.next==null){
break; //
}
if(temp.next.no==node.no){ //
flag=true;
break;
}
temp=temp.next;//
}
if(flag){
temp.next=temp.next.next;
}else{
System.out.println(" : "+node);
}
}
/**
*
* @return
*/
public int getAllNodeNumber(){
int num=0;
if(head.next==null) return 0;
Node temp=head.next;
while (true){
if(temp==null){
break;
}
num++;
temp=temp.next;
}
return num;
}
/**
* K ( : , first k-1 , second , , K )
*/
public void getLastK(int k){
if(head.next==null) System.out.println(" ");
Node first=head;
Node second=head;
for (int i = 0; i < k-1; i++) {
if(first.next==null) return;
first=first.next;
}
while(first.next!=null){
first=first.next;
second=second.next;
}
System.out.println(second);
}
/**
*
*/
public void InverseList(){
if(head.next==null) {
System.out.println(" , ");
return;
}
Node temp=head; // temp list
Node newTemp=head; // newTemp
Stack<Node> stack=new Stack<>(); //
while(temp.next!=null){ //
stack.push(temp.next);
temp=temp.next;
}
while(!stack.empty()){ // , , ( )
newTemp.next=stack.pop();
newTemp=newTemp.next;
}
// while (stack.size()>0){ // ,
// System.out.println(stack.pop());
// }
newTemp.next=null; // next ,
}
/**
*
*/
public void reverse() {
if (head.next == null || head.next.next == null)
return ;
Node cur=head.next;
Node next=null;
Node reserve=new Node(-1,"");
while(cur!=null){
next=cur.next;
cur.next=reserve.next;
reserve.next=cur;
cur=next;
}
head.next=reserve.next;
}
/**
*
* @param list1
* @param list2
* @return
*/
public Node mergeList(Node list1,Node list2){
if(list1==null) return list2; // ,
if(list2==null) return list1;
Node newNode=new Node(-1,""); //
Node temp=newNode; // ,
while((list1!=null)&&(list2!=null)){ //
if(list1.no>=list2.no){ // list1.no>=list2.no
temp.next=list2; // ,
list2=list2.next;
}
else {
temp.next=list1;
list1=list1.next;
}
temp=temp.next; //
}
// if(list1==null){
// temp.next=list2;
// }
// else if (list2==null){
// temp.next=list1;
// }
temp.next=list1==null?list2:list1; // ,
return newNode.next; //
}
/**
*
* @param list1
* @param list2
* @return
*/
public Node mergeListDigui(Node list1,Node list2){
if(list1==null) return list2;
if(list2==null) return list1;
if(list1.no<list2.no){
list1.next= mergeListDigui(list1.next,list2);
return list1;
}else {
list2.next = mergeListDigui(list1, list2.next);
return list2;
}
}
}
//
public class LinkListDemo {
public static void main(String[] args) {
Node node=new Node(1,"kaikai");
Node node1=new Node(2,"kaikai");
Node node2=new Node(4,"kaikai");
LinkedListDemo list=new LinkedListDemo();
// list.addOrder(node);
// list.addOrder(node1);
// list.addOrder(node2);
// list.prtList(); //
Node node3=new Node(2,"kaikai1");
Node node4=new Node(3,"kaikai");
Node node5=new Node(8,"kaikai");
node.next=node1;
node1.next=node2;
node3.next=node4;
node4.next=node5;
//
Node node6 = list.mergeListDigui(node, node4);
while(node6!=null){
System.out.println(node6);
node6=node6.next;
}
// final int allNodeNumber = list.getAllNodeNumber();
// System.out.println(" : "+allNodeNumber);
//
// System.out.println(" : ");
// list.reverse();
// list.prtList();
//
// System.out.println(" K : ");
// list.getLastK(3);
//
// System.out.println(" :");
// Node node5=new Node(5,"kaikai55555");
// list.updateNode(node5);
// list.prtList();
//
// System.out.println(" :");
// Node node6=new Node(5,"kaikai55555");
// list.deleteNode(node6);
// list.prtList();
}
}
奴らはスプレーを見てひざまずいた