将二个单链表合并成一个单链表 原理
时间: 2024-05-22 10:11:29 浏览: 14
合并两个单链表的原理是通过遍历两个单链表,比较每个节点的值大小,将较小的节点插入到新的单链表中,直到其中一个单链表遍历完为止。然后将未遍历完的单链表剩余部分直接添加到新的单链表末尾。
具体的实现步骤如下:
1. 定义一个新的单链表,用来存放合并后的结果。
2. 定义三个指针,分别指向两个单链表的当前节点和新单链表的尾节点。
3. 比较两个当前节点的值大小,将较小的节点插入到新单链表的尾节点后面。
4. 将新单链表的尾节点指针移动到新插入的节点上。
5. 将当前节点指针向后移动,继续比较,直到其中一个单链表遍历完。
6. 将未遍历完的单链表的剩余部分直接添加到新单链表的尾部。
7. 返回新单链表的头节点,即为合并后的结果。
需要注意的是,两个单链表的节点值类型应该是可比较的,否则无法进行比较插入操作。同时,为了避免破坏原有的单链表结构,可以新建一个节点来存放合并后的结果,而不是直接修改原有的单链表。
相关问题
将两个单链表合并成一个单链表
以下是将两个单链表合并成一个单链表的Python实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 创建一个新的链表头结点
dummy = ListNode(0)
# 创建一个指针指向新链表的头结点
cur = dummy
# 当两个链表都不为空时,比较两个链表的头结点的大小,将较小的结点连接到新链表的后面
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 将剩余的结点连接到新链表的后面
cur.next = l1 if l1 else l2
# 返回新链表的头结点
return dummy.next
```
将两个有序单链表合并成一个有序单链表
可以使用双指针法,分别指向两个链表的头节点,比较两个节点的值大小,将较小的节点加入新的链表中,然后将指针指向较小节点的下一个节点,直到其中一个链表遍历完毕,将剩余的节点加入新链表中即可。最后返回新链表的头节点即可。
具体实现可以参考以下代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy.next
```
其中,dummy节点用于指向新链表的头节点,cur节点用于指向新链表的尾节点,便于添加新节点。