合并两个有序的链表
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 = None
class 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
如果您感觉本文有用,请点个“在看”