java实现链表升序合并

解题思路： 1.用输入的数据创建好两个链表。

2.将两个无序链表合并成一个链表：用一个变量记录链表1的尾结点，使其下个节点指向链表2。

3. 对合并后的链表进行排序：排序采取排序算法中的归并排序。个人认为对于链表排序实现采取递归方式较为容易。

注意事项:1. 创建好结点类，成员变量为学号，成绩，和用于指向下一个节点的变量。

              2. 注意结点指向问题，局域变量作用范围

              3. 递归的退出条件

参考代码:

import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int i1 = sc.nextInt();
       int i2 = sc.nextInt();
       ListNode list1 = new ListNode(sc.nextInt(),sc.nextInt());
       ListNode head1 = list1;
       for (int i = 0; i < i1-1; i++) {
           head1.next = new ListNode(sc.nextInt(),sc.nextInt());

// 确保head1为链表1的尾节点
           if (i!=i1-1) {
               head1 = head1.next;
           }
       }

       ListNode list2 = new ListNode(sc.nextInt(),sc.nextInt());
       ListNode head2 = list2;
       for (int i = 0; i < i2-1; i++) {
           head2.next = new ListNode(sc.nextInt(), sc.nextInt());

// head2为链表2的尾节点
           if (i != i2 - 1) {
               head2 = head2.next;
           }
       }

// 链表1的尾节点的下一节点指向链表2
       head1.next = list2;

//        上面为合并两个链表为一个无序链表，下面对其进行归并排序
       list1 = merge(list1);

// 循环输出节点属性
       while (list1!=null){
           System.out.println(list1.id+" "+ list1.grade);
           list1 =list1.next;
       }
   }

// 归并排序中的合并排序操作（相当于对两个有序链表合并成一个有序链表）
   public static ListNode sort(ListNode l1,ListNode l2){

// 当两个链表中其中一个链表为空则返回另一个链表（递归退出条件）
       if (l1==null){
           return l2;
       }
       if (l2==null){
           return l1;
       }

// 学号小的结点指向学号大的结点
       if (l1.id<l2.id){

    // 将 l1（学号小的头结点）的下一个结点作为下一个递归中的头结点 l1, l2 不改变
           l1.next = sort(l1.next,l2);

    // 将当前分链表的头节点返回
           return l1;
       }else {
            l2.next = sort(l1,l2.next);
           return l2;
       }
   }

// 归并排序中的拆分操作
   public static ListNode merge(ListNode head){

// 头节点为空或下一个结点为空返回头节点（递归退出条件）
       if (head==null || head.next==null){
           return head;
       }

// 快慢指针 （用于寻找链表的中间结点，即移动完后慢指针slow是中间结点）

       ListNode slow = head;            
       ListNode fast =head;                   
// 当fast的下一个结点为空（链表结点个数为偶数情况）或fast的下下个结点为空（链表结点个数为奇数情况）                

       while (true){
           if (fast.next==null || fast.next.next==null){    
               break;
           }                                  

// 慢指针每次移动一次 快指针每次移动两次，可以较为均匀的分成两个链表                              
           slow = slow.next; 
           fast = fast.next.next; 
       }                                                                                                                                                                            

// head 到slow 为 l1 链表，slow.next到fast为 l2 链表           
       ListNode l1 = head; 
       ListNode l2 = slow.next;     

// 拆分成两个链表，将 l1 链表的尾节点slow的下一个节点指向null

       slow.next =null;

//继续拆分直到为单个节点为止
       l1 = merge(l1);
       l2 = merge(l2);

// 返回合并排序过后的链表头节点
       return sort(l1,l2);
   }
}

//结点类

class ListNode {
   int id;
   int grade;

//用于指向下一个节点
   ListNode next;
   ListNode() {}
   ListNode(int val,int grade) { this.id = val; this.grade=grade;}
   ListNode(int val, ListNode next) { this.id = val; this.next = next; }
}