合并两个有序的链表
1. 题目形容
输出两个枯燥递增的链表，输入两个链表合成后的链表，当然咱们须要合成后的链表满足枯燥不减规定。
2. 示例
无
3. 解题思路
思路：非递归
比拟两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前挪动一个结点。
步骤一后果会有一个链表先遍历完结，或者没有
第三个链表尾结点指向残余未遍历完结的链表
返回第三个链表首结点
递归办法：
4. Java实现
非递归的实现办法：应用一个辅助的头部节点： ListNode root = new ListNode(-1)
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } ListNode node = new ListNode(-1); // 用于保留头部节点 ListNode root = node; while (list1 != null && list2 != null){ if (list1.val < list2.val){ node.next = list1; node = node.next; // 更新node节点，指向下一个 list1 = list1.next; }else{ node.next = list2; node = node.next; list2 = list2.next; } } // 可能某个链表还残余值,下列例子就链表2 会残余 // 比方链表1： 1->2->4 // 链表2： 3->5->6 if(list1 == null){ node.next = list2; } if (list2 == null){ node.next = list1; } return root.next; }}应用递归的实现办法：
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } ListNode ret = null; if (list1.val < list2.val){ ret = list1; ret.next = Merge(list1.next, list2); }else{ ret = list2; ret.next = Merge(list1, list2.next); } return ret; }}5. Python实现
比较简单的非递归的实现办法：
#非递归实现合并两个有序的链表class Solution1: # 返回合并后列表 def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 start = None p = None while pHead1 and pHead2: if pHead1.val <= pHead2.val: print(pHead1.val) if start is None: start = p = pHead1 else: p.next = pHead1 p = p.next #更新p 结点 pHead1 = pHead1.next # 更新有序链表的结点 else: if start is None: start = p = pHead2 else: p.next = pHead2 p = p.next pHead2 = pHead2.next #可能某个链表始终还剩值 if not pHead1: #如果第一个链表都是空的话 p.next = pHead2 else: p.next = pHead1 return start 应用递归的实现办法：
# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here if not pHead1: #如果一个链表不存在的话，返回另外一个链表 return pHead2 if not pHead2: return pHead1 if pHead1.val <= pHead2.val: ret = pHead1 ret.next = self.Merge(pHead1.next, pHead2) else: ret = pHead2 ret.next = self.Merge(pHead1, pHead2.next) return ret 如果您感觉本文有用，请点个“在看”