實作一個單鏈表，鏈表初始為空，支持三種操作：
(1) 向鏈表頭插入一個數；
(2) 洗掉第k個插入的數后面的數
(3) 在第k個插入的數后插入一個數
現在要對該鏈表進行M次操作，進行完所有操作后，從頭到尾輸出整個鏈表，
注意:題目中第k個插入的數并不是指當前鏈表的第k個數，例如操作程序中一共插入了n個數，則按照插入的時間順序，這n個數依次為：第1個插入的數，第2個插入的數，…第n個插入的數，
輸入格式
第一行包含整數M，表示操作次數，
接下來M行，每行包含一個操作命令，操作命令可能為以下幾種：
(1) “H x”，表示向鏈表頭插入一個數x，
(2) “D k”，表示洗掉第k個輸入的數后面的數（當k為0時，表示洗掉頭結點），
(3) “I k x”，表示在第k個輸入的數后面插入一個數x（此操作中k均大于0），
輸出格式
共一行，將整個鏈表從頭到尾輸出，
資料范圍
1≤M≤1000001≤M≤100000
所有操作保證合法，
輸入樣例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
輸出樣例：
6 4 6 5
思路：手動模擬一下；
下標從0開始(2) 洗掉第k個插入的數后面的數-->就是洗掉第k-1個數后面的那個數(3) 在第k個插入的數后插入一個數-->就是在第k-1個數后面插入一個數 import java.util.Scanner; public class Main{ static final int max=100005; static int e[]=new int[max];//存盤結點i的值 static int ne[]=new int[max];//存盤結點i的下一個指標是什么 static int idx,head;//idx表示用到當前哪個結點；head表示頭結點 public static void init(){//初始化 head=-1; idx=0; } public static void add_head(int x){//頭插法頭部插入一個結點 e[idx]=x; ne[idx]=head; head=idx; idx++; } public static void add(int k,int x){//在第k個結點后插入一個結點 e[idx]=x; ne[idx]=ne[k]; ne[k]=idx; idx++; } public static void del(int k){//洗掉第k個結點后那個結點 ne[k]=ne[ne[k]]; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); init();//初始化 int m=scan.nextInt(); while(m-->0){ String s=scan.next(); if(s.equals("H")){//字串判斷相等一定不要用== int x=scan.nextInt(); add_head(x); } else if(s.equals("D")){ int k=scan.nextInt(); if(k==0) head=ne[head]; else del(k-1); } else if(s.equals("I")){ int k=scan.nextInt(); int x=scan.nextInt(); add(k-1,x); } } for(int i=head;i!=-1;i=ne[i]) System.out.print(e[i]+" "); System.out.println(); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103932.html
標籤：其他
上一篇：易錯之 Java字串比較
下一篇：網站如何實作短信驗證碼功能？