递增量表的创建、合并、打印

分类: IT文章 • 2023-11-21 23:08:42

1、链表节点类

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

View Code

2、链表合并类

public class ListMerge {
    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode head = null;

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

       //递归调用
        if (list1.val < list2.val) {
            head = list1;
            head.next = merge(list1.next, list2);
        } else {
            head = list2;
            head.next = merge(list1, list2.next);
        }

        return head;

    }
}

View Code

3、链表打印类

import java.util.ArrayList;
import java.util.Stack;

public class PrintList {
    //方式一：通过将链表所有节点存入ArrayList中，然后遍历ArrayList中输出的元素
    public void printList(ListNode head) {
        //遍历链表所有节点，存入ArrayList中
        ArrayList<ListNode> arrayList2 = new ArrayList<ListNode>();
        while (head != null) {
            arrayList2.add(head);
            head = head.next;
        }
        //输出值
        for (int i = 0; i < arrayList2.size(); i++) {
            System.out.print(arrayList2.get(i).val + " ");
        }
    }

    //方式二：通过将链表所有节点压入栈中，然后弹出所有节点的值，实现链表逆序打印
    public void printList2(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        //链表所有节点进栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        //打印栈中所有节点的值
        while (!stack.empty()) {
            System.out.print(stack.pop().val+" ");

        }
    }
}

View Code

4、测试类（含链表创建）

public class TestMain {
    public static void main(String[] args) {
        //创建打印链表类的对象
        PrintList p=new PrintList();

        //新建链表1
        ListNode head1=new ListNode(1);
        ListNode node11=new ListNode(3);
        ListNode node12=new ListNode(5);
        ListNode node13=new ListNode(7);
        head1.next=node11;
        node11.next=node12;
        node12.next=node13;
        node13.next=null;
        //打印链表1
        p.printList(head1);
        System.out.println();

        //新建链表2
        ListNode head2=new ListNode(2);
        ListNode node21=new ListNode(4);
        ListNode node22=new ListNode(6);
        ListNode node23=new ListNode(8);
        head2.next=node21;
        node21.next=node22;
        node22.next=node23;
        node23.next=null;
        //打印链表2
        p.printList(head2);
        System.out.println();

        //链表合并
        ListMerge listMerge=new ListMerge();
        ListNode head=listMerge.merge(head1,head2);

        //打印合并后的链表
        p.printList(head);
    }
}

View Code

递增量表的创建、合并、打印

相关推荐