链表归并排序

解题思路:

注意事项:

参考代码:

import java.util.*;

class ListNode {

int id;

int grand;

ListNode next;

public ListNode() {

};

public ListNode(int id, int grand) {

this.id = id;

this.grand = grand;

}

}

public class wc {

static Scanner sc = new Scanner(System.in);;

public static void main(String[] args) {

int N=sc.nextInt();

int M=sc.nextInt();

//初始化头

ListNode list1=new ListNode(sc.nextInt(),sc.nextInt());

//定义尾节点

ListNode head1=list1;

for(int i=0;i<N-1;i++) {

head1.next=new ListNode(sc.nextInt(),sc.nextInt());

head1=head1.next;

}

ListNode list2=new ListNode(sc.nextInt(),sc.nextInt());

ListNode head2=list2;

for(int i=0;i<M-1;i++) {

head2.next=new ListNode(sc.nextInt(),sc.nextInt());

head2=head2.next;

}

head1.next=list2;

ListNode list3=mergesort(list1);

show(list3);

}

//找链表中点

static ListNode mid(ListNode list) {

if(list==null||list.next==null)

return list;

ListNode slow,fast;

slow=list;

fast=list.next;

while(fast!=null&&fast.next!=null) { //俩个&&后一个不做判断,所以不会出现空指针

slow=slow.next;

fast=fast.next.next;

}

return slow;

}

//合并

static ListNode merge(ListNode list1,ListNode list2) {

if(list1==null)

return list2;

if(list2==null)

return list1;

ListNode list3=new ListNode();

ListNode list4=list3;

while(list1!=null&list2!=null) {

if(list1.id>list2.id) {

list4.next=list2;

list2=list2.next;

}else {

list4.next=list1;

list1=list1.next;

}

list4=list4.next;

}

if(list1!=null)

list4.next=list1;

else

list4.next=list2;

return list3.next;

}

//排序

static ListNode mergesort(ListNode list) {

if(list==null|list.next==null)

return list;

ListNode mid=mid(list);

ListNode list1=mid.next;

mid.next=null;

ListNode left=mergesort(list);

ListNode right=mergesort(list1);

return merge(left,right);

}

//输出

static void show(ListNode list) {

ListNode list1=list;

while(list1!=null) {

System.out.println(list1.id+" "+list1.grand);

list1=list1.next;

}

}

}