Java 单链表-有序链表的插入、两个升序表合并成降序表

我不是女神ヾ 2022-11-21 09:54 196阅读 0赞

设计存储int型数据的带头结点的单链表List。要求：

1.  实现输入一组数，以-1结束，
2.  实现void merge(L)操作：将两个升序表合并成降序表
3.  定义一个方法，实现向升序表中插入元素x，插入后依旧是升序表
4.  打印出单链表的所有元素

import java.util.Scanner;
    class List{
        
    	int data;
    	List next;
    	List(int x){
         data = x;}
    	void append(){
        
    		List tail,p;
    		System.out.println("请输入一组数，以-1结尾：");
    		Scanner sc = new Scanner(System.in);
    		int x = sc.nextInt();
    		tail = this;
    		while(x != -1) {
        
    			p = new List(x);
    			tail.next = p;
    			tail = p;
    			x = sc.nextInt();
    		}
    	}
    	void print() {
        
    		for(List p=this.next; p!=null; p=p.next)
    			System.out.print(p.data+" ");
    		System.out.print("\n");
    	}
    	void merge(List L) {
         //两个升序表合并为降序表，用头插法
    		List newL = new List(0);
    		List f;
    		List h1 = this.next;
    		List h2 = L.next;
    		while(h1!=null && h2!=null) {
        
    			if(h1.data < h2.data) {
        
    				f = h1;
    				h1 = h1.next;
    			}
    			else {
        
    				f = h2;
    				h2 = h2.next;
    			}
    			f.next = newL.next;
    			newL.next = f;
    		}
    		while(h1!=null) {
        
    			f = h1; 
    			h1=h1.next;
    			f.next = newL.next;
    			newL.next = f;
    		}
    		while(h2!=null) {
        
    			f = h2; 
    			h2=h2.next;
    			f.next = newL.next;
    			newL.next = f;
    		}
    		this.next = newL.next;
    	}
    	void insert() {
        
    		System.out.println("请输入待插入的数：");
    		Scanner sc = new Scanner(System.in);
    		int x = sc.nextInt();
    		List pre,f,q;
    		pre = this;  f = this.next;
    		q = new List(x);
    		while(f!=null && x>f.data) {
        
    			pre = f; 
    			f = f.next;
    		}
    		q.next = pre.next; //因 pre.data< x< f，将f插入pre之后、f之前
    		pre.next = q;
    	}
    }
    class App{
        
    	public static void main(String [] args) {
        
    		List h = new List(0);
    		h.append();
    		h.print();
    		List s = new List(0);
    		s.append();
    		s.print();
    		h.insert();
    		System.out.println("插入结果为：");
    		h.print();
    		h.merge(s);
    		System.out.println("合并结果为：");
    		h.print();
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e1d06664272d49f9bf0c49b3a0c2e3c9.png