17_合并两个有序链表

痛定思痛。 2022-06-07 01:39 91阅读 0赞

> 题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

import java.util.Scanner;
    
    //链表的结构
    class LinkedList {
        int data;
        LinkedList next;
    }
    
    public class UnionLinkList{
        // 建立单链表
        // 输入的参数：单链表的头结点
        public static void createLinkedList(LinkedList cur,int k) {
            Scanner scanner = new Scanner(System.in);
            String data;
            System.out.println("输入单链表"+k+"，以#结束(输入完最后一个结点，仍需要空格，再加#):");
            while (true) {
                data = scanner.next();
                if (data.equals("#")) {
                    cur.next = null;
                    break;
                }
                LinkedList node = new LinkedList();
                node.data = Integer.valueOf(data);
                cur.next = node;
                cur = cur.next;
            }
        }
    
        // 合并后的链表
        // 输入的参数：链表a,链表b,合并后的链表
        public static LinkedList union(LinkedList a,LinkedList b,LinkedList union){
            LinkedList pc = union = a;
            LinkedList pa = a.next;
            LinkedList pb = b.next;
            while(pa != null && pb != null){
                if(pa.data < pb.data){
                    pc.next = pa;
                    pc = pa;
                    pa = pa.next;
                }else{
                    pc.next = pb;
                    pc = pb;
                    pb = pb.next;               
                }
                if(pa != null){
                    pc.next = pa;
                }
                if(pb != null){
                    pc.next = pb;
                }
            }
            return union;
        }
    
        // 打印单链表
        // 输入的参数：链表头指针
        public static void printLinkList(LinkedList head){
            if(head == null || head.next == null){
                return;
            }
            head = head.next;
            while(head != null){
                System.out.print(head.data+" ");
                head = head.next;
            }
            System.out.println();
        }
    
       public static void main(String[] args) {
            LinkedList a = new LinkedList();
            LinkedList b = new LinkedList();
            createLinkedList(a,1);
            createLinkedList(b,2);
            LinkedList union = null;
            union = union(a,b, union);
            System.out.println("排序后链表：");
            printLinkList(union);
        }
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/2508f39bb33942769a22181734a0fd65.png