杂谈——如何合并两个有序链表（时间复杂度为O(n)）

Love The Way You Lie 2022-04-04 15:58 103阅读 0赞

假设本帅博主有链表arr1：

int[] arr1 = {1,3,6,8,23,34,56,77,90};

链表arr2：

int[] arr2 = {-90,34,55,79,87,98,123,234,567};

我要如何才能够合并这两个有序链表，使得合并后的链表有序，并且使算法的时间复杂度为O(n)呢？

思考一下噢~

.......

本帅博主也就不说别的啦，直接上代码：

Node类：

public class Node 
    {
    	private Node next;
    	private Integer number;
    	Node(Integer number)
    	{
    		this.number=number;
    		next=null;
    	}
    	Node()
    	{
    		
    	}
    	public Node getNext() {
    		return next;
    	}
    	public void setNext(Node next) {
    		this.next = next;
    	}
    	public Integer getNumber() {
    		return number;
    	}
    	public void setNumber(Integer number) {
    		this.number = number;
    	}
    	
    }

算法实现：

public class SortForLink {
    	static int a=0;
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] arr1 = {1,3,6,8,23,34,56,77,90};
    		int[] arr2 = {-90,34,55,79,87,98,123,234,567};
    		Node link1 = new Node();
    		Node link2 = new Node();
    		Node link3 = new Node();
    		getLink(arr1,link1);
    		getLink(arr2,link2);
    		mergeLink(link1, link2, link3);
    		viewLink(link3);
    	}
    	
    	/**
    	 * 构建链表
    	 * @param arr
    	 * @param link
    	 */
    	public static void getLink(int[] arr, Node link) {
    		for(int i = 0; i < arr.length; i++) {
    			link.setNumber(arr[i]);
    			link.setNext(new Node());
    			link = link.getNext();
    		}
    	}
    	
    	/**
    	 * 输出链表
    	 * @param link
    	 */
    	public static void viewLink(Node link) {
    		while(link.getNumber() != null) {
    			System.out.print(link.getNumber()+" ");
    			link = link.getNext();
    		}
    		System.out.println("a的值是："+a);
    	}
    	
    	/**
    	 * 合并链表
    	 * @param link1
    	 * @param link2
    	 * @param link3
    	 */
    	public static void mergeLink(Node link1, Node link2, Node link3) {
    		
    		if( (link2.getNumber() != null) && (link1.getNumber() == null || link1.getNumber() >= link2.getNumber()) ) {
    			link3.setNumber(link2.getNumber());
    			link3.setNext(new Node());
    			link2 = link2.getNext();
    			link3 = link3.getNext();
    			a++;
    			mergeLink(link1, link2, link3);
    		}else if( (link1.getNumber() != null) && (link2.getNumber() == null || link2.getNumber() > link1.getNumber()) ) {
    			link3.setNumber(link1.getNumber());
    			link3.setNext(new Node());
    			link1 = link1.getNext();
    			link3 = link3.getNext();
    			a++;
    			mergeLink(link1, link2, link3);
    		}else {
    			System.out.println("==没有了，结束啦！==");
    		}		
    	}
    }

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlYXJjaGluX1I_size_16_color_FFFFFF_t_70][]

好啦，以上就是关于如何合并两个有序链表为一个有序链表并使时间复杂度为O(n)的算法相关知识总结啦，如果大家有什么不明白的地方或者发现文中有描述不好的地方，欢迎大家留言评论，我们一起学习呀。

***Biu~~~~~~~~~~~~~~~~~~~~![å®«å´éªé¾ç«è¡¨æå|é¾ç«gifå¾è¡¨æåä¸è½½å¾ç][gif]~~~~~~~~~~~~~~~~~~~~~~pia！***

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlYXJjaGluX1I_size_16_color_FFFFFF_t_70]: /images/20220404/2177e2ed9a0540f68568e168b9129e06.png
[gif]: /images/20220404/1d59fb99129e467fa090bad5939f7843.png