2019-03-21-算法-进化（合并两个有序链表）

た入场券 2022-03-01 06:08 103阅读 0赞

**题目描述**  
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

思路1：双指针法

/**
    	 * 合并两个有序链表（默认为升序）
    	 * 双指针法
    	 * @param l1
    	 * @param l2
    	 * @return
    	 */
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if(l1 == null) {
    			return l2;
    		}
    		if(l2 == null) {
    			return l1;
    		}
    		ListNode head = new ListNode(-1);
    		ListNode index = head;
    		while(l1!=null && l2!=null) {
    			if(l1.val>l2.val) {
    				index.next = l2;
    				l2=l2.next;
    			}else {
    				index.next = l1;
    				l1 = l1.next;
    			}
    			index = index.next;
    		}
    		if(l1!=null) {
    			while (l1!=null) {
    				index.next = l1;
    				l1 = l1.next;
    				index = index.next;
    			}
    		}
    		if(l2!=null) {
    			while (l2!=null) {
    				index.next = l2;
    				l2 = l2.next;
    				index = index.next;
    			}
    		}
    		return head.next;
        }

思路1代码优化版（**代码短了，耗时反而增加了**，应该是if else的判断多了导致的）

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if(l1 == null) {
    			return l2;
    		}
    		if(l2 == null) {
    			return l1;
    		}
    		ListNode head = new ListNode(-1);
    		ListNode index = head;
    		while(l1!=null || l2!=null) {
    			if(l1 !=null && l2!=null) {
    				if(l1.val>l2.val) {
    					index.next = l2;
    					l2=l2.next;
    				}else {
    					index.next = l1;
    					l1 = l1.next;
    				}
    			}else if (l1 != null && l2==null) {
    				index.next = l1;
    				l1 = l1.next;
    			}else if (l1 == null && l2!=null) {
    				index.next = l2;
    				l2=l2.next;
    			}
    			
    			index = index.next;
    		}
    		return head.next;
        }

思路1优化版，**优化了时间**

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if(l1 == null) {
    			return l2;
    		}
    		if(l2 == null) {
    			return l1;
    		}
    		ListNode head = new ListNode(-1);
    		ListNode index = head;
    		while(l1!=null && l2!=null) {
    			if(l1.val>l2.val) {
    				index.next = l2;
    				l2=l2.next;
    			}else {
    				index.next = l1;
    				l1 = l1.next;
    			}
    			index = index.next;
    		}
    		//任一为空，直接链接另一个链表
    		if(l1!=null) {
    			index.next=l1;
    		}else {
    			index.next=l2;
    		}
    		return head.next;
        }