合并两个已经排序好的链表

2019-11-08 02:28:20

字体：大中小

来源：转载

供稿：网友

一，问题描述 1，输入两个单调递增的链表，输出两个链表合成后的链表。新链表也是单调递增的。

二，程序如下(java实现）：

1，非递归合并有序链表

import java.util.*;class ListNode{ int val; ListNode next; ListNode(int x) { val=x; }}public class Test{ public ListNode Merge(ListNode node1,ListNode node2) { if(node1==null&&node2==null) { return null; } if(node1==null) { return node2; } if(node2==null) { return node1; } ListNode node3=null; //这个作为偏移指针 ListNode node4=null; //这个作为头指针 while(node1!=null&&node2!=null) { if(node1.val<=node2.val) { if(node4==null) { node3=node1; node4=node1; } else { node3.next=node1; node3=node3.next; } node1=node1.next; } else { if(node4==null) { node3=node2; node4=node2; } else { node3.next=node2; node3=node3.next; } node2=node2.next; } } if(node1!=null) { node3.next=node1; } if(node2!=null) { node3.next=node2; } return node4; } public static void main(String []args) { Test test=new Test(); ListNode node11=new ListNode(1); ListNode node12=new ListNode(3); ListNode node13=new ListNode(5); ListNode node14=new ListNode(7); ListNode node15=new ListNode(9); ListNode node21=new ListNode(2); ListNode node22=new ListNode(4); ListNode node23=new ListNode(6); ListNode node24=new ListNode(8); ListNode node25=new ListNode(10); node11.next=node12; node12.next=node13; node13.next=node14; node14.next=node15; node21.next=node22; node22.next=node23; node23.next=node24; node24.next=node25; ListNode node=test.Merge(node11,node22); while(node!=null) { System.out.PRint(node.val+"->"); node=node.next; } }}

2，递归方式合并有序链表

import java.util.*;class ListNode{ int val; ListNode next; ListNode(int x) { val=x; }}public class Test{ public ListNode Merge(ListNode node1,ListNode node2) { if(node1==null) { return node2; } if(node2==null) { return node1; } if(node1.val<=node2.val) { node1.next=Merge(node1.next,node2); return node1; } else { node2.next=Merge(node1,node2.next); return node2; } } public static void main(String []args) { Test test=new Test(); ListNode node11=new ListNode(1); ListNode node12=new ListNode(3); ListNode node13=new ListNode(5); ListNode node14=new ListNode(7); ListNode node15=new ListNode(9); ListNode node21=new ListNode(2); ListNode node22=new ListNode(4); ListNode node23=new ListNode(6); ListNode node24=new ListNode(8); ListNode node25=new ListNode(10); node11.next=node12; node12.next=node13; node13.next=node14; node14.next=node15; node21.next=node22; node22.next=node23; node23.next=node24; node24.next=node25; ListNode node=test.Merge(node11,node22); while(node!=null) { System.out.print(node.val+"->"); node=node.next; } }}

输出结果： 1->2->3->4->5->6->7->8->9->10

上一篇：五子棋

下一篇：C语言结构体的定义以及使用