我是靠谱客的博主 还单身蜜蜂,最近开发中收集的这篇文章主要介绍数据结构——链表(一)Leetcode刷题java之21. 合并两个有序链表,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

Leetcode刷题java之21. 合并两个有序链表

解法一:

class ListNode {
    int val;
    ListNode next;     
    ListNode(int x) { val = x; }
}
public class Solution_2 {
	public  void mergeTwoLists(ListNode n1,ListNode n2) {
		ListNode newNode = new ListNode(0);
		ListNode cur = newNode;
		while(n1!=null && n2!=null) {
			if(n1.val < n2.val) {
				cur.next = n1;
				cur = cur.next;
				n1 = n1.next;
			}else {
				cur.next = n2;
				cur = cur.next;
				n2 = n2.next;
			}
		}
		//任一为空,直接连接另条表
		if(n1 == null) {
			cur.next = n2;
		}else {
			cur.next = n1;
		}
		cur=newNode.next;
		System.out.print("l3: ");
    	while(cur!=null) {
    		System.out.print(cur.val);
    		cur=cur.next;
    	}
    	System.out.println();
		
	}
	public static void main(String[]args) {
    	//l1初始化
    	ListNode l1=new ListNode(1);//新建节点
    	ListNode pre=l1;//创建头指针

    	pre.next=new ListNode(2);
    	pre=pre.next;//移动指针
   	
    	pre.next=new ListNode(5);
    	pre=pre.next;
    
    	//l2初始化
    	ListNode l2=new ListNode(1);
    	ListNode pre2=l2;
    	
    	pre2.next=new ListNode(3);
    	pre2=pre2.next;
    
    	
    	pre2.next=new ListNode(6);
    	pre2=pre2.next;
   
    	
    	Solution_2 s = new Solution_2();
    	
    	
    	s.mergeTwoLists( l1, l2);
    	//l1被破坏
    	System.out.print("l1: ");
    	pre=l1;
      	while(pre!=null) {
    		System.out.print(pre.val);
    		
    		pre=pre.next;
    	}
      	System.out.println();
      	
      	//l2被破坏
      	System.out.print("l2: ");
      	pre2=l2;
      	while(pre2!=null) {
    		System.out.print(pre2.val);
    		pre2=pre2.next;
    	}
      	System.out.println();
    	
    }
	
}

但解法一有明显的不足。在原程序中,l1:1->2->5,l2:  1->3->6。

但在执行完后,l1 l2均被改变。

通过测试程序不难发现,l1 l2已经被破坏。

解法二:新建l3链表,并且使得l1 l2保持原样

/*本程序在不破坏l1 l2的基础上,新建了l3链表
 * 
 * */
//ListNode数据结构定义
class ListNode {
     int val;
     ListNode next;     
     ListNode(int x) { val = x; }
 }
public class Solution {
    public void mergeTwoLists(ListNode l1, ListNode l2) {
    	ListNode l3=new ListNode(0);
    	/*创建l3头节点
    	 * 由于ListNode没有无参的构造函数,所以参数写0
    	 * 返回时从第二个节点返回即可 */
   
    	ListNode pre=l3;//创建指针
    	ListNode pre1=l1;
    	ListNode pre2=l2;

    	while(pre1!=null&&pre2!=null) {
    		if(pre1.val<=pre2.val)   {
    			pre.next=new ListNode(pre1.val);
    			pre=pre.next;
    			pre1=pre1.next;
    			//l3=l3.next;
    		}
    		else {
    			pre.next=new ListNode(pre2.val);
    			pre=pre.next;
    			pre2=pre2.next;
    		}    		
    	}
    	if(pre1==null) {
        	while(pre2!=null) {
    	    	pre.next=new ListNode(pre2.val);
    	    	pre=pre.next;
    	    	pre2=pre2.next;
    	    		//l2=l2.next;
        	}	
        }
        if(pre2==null) {
        	while(pre1!=null) {
	        	pre.next=new ListNode(pre1.val);
	        	pre=pre.next;
	        	pre1=pre1.next;
        	}
        }
    	
    	
    	//对l3输出
    	pre=l3.next;
    	while(pre!=null) {
    		System.out.print(pre.val);
    		pre=pre.next;
    	}
    	System.out.println();
    }
    public static void main(String[]args) {
    	//l1初始化
    	ListNode l1=new ListNode(1);//新建节点
    	ListNode pre=l1;//创建头指针

    	pre.next=new ListNode(2);
    	pre=pre.next;//移动指针
   	
    	pre.next=new ListNode(5);
    	pre=pre.next;
    
    	//l2初始化
    	ListNode l2=new ListNode(1);
    	ListNode pre2=l2;
    	
    	pre2.next=new ListNode(3);
    	pre2=pre2.next;
    
    	
    	pre2.next=new ListNode(6);
    	pre2=pre2.next;
   
    	
    	Solution s = new Solution();
    	
    	//l1可正常输出
    	s.mergeTwoLists( l1, l2);
    	System.out.println();
    	pre=l1;
      	while(pre!=null) {
    		System.out.print(pre.val);
    		
    		pre=pre.next;
    	}
      	System.out.println();
      	
      	//l2可正常输出
      	pre2=l2;
      	while(pre2!=null) {
    		System.out.print(pre2.val);
    		pre2=pre2.next;
    	}
      	System.out.println();
    	
    }
    
}

输出结果如下:

由结果可知,l1 l2并没有被改变。

但缺点多使用了内存空间。

解法三:递归调用


class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
        {
            return l2;
        }
        if(l2==null)
        {
            return l1;
        }
        if(l1.val<l2.val)
        {
            l1.next=mergeTwoLists(l1.next,l2);//递归
            return l1;
        }else
        {
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

}

 

最后

以上就是还单身蜜蜂为你收集整理的数据结构——链表(一)Leetcode刷题java之21. 合并两个有序链表的全部内容,希望文章能够帮你解决数据结构——链表(一)Leetcode刷题java之21. 合并两个有序链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(62)

评论列表共有 0 条评论

立即
投稿
返回
顶部