合并两个排序的链表(双指针)

图片文字说明



思路

  • 有比较单纯的一种思路,那就是先把这两个链表全部转化成python的list,然后进行sort,然后进行链表的合成,但是这个太麻烦了
  • 第二种思路就是通过双指针
  • 因为题目说了,L1和L2都是递增的,那其实可以遍历L1 和 L2,通过 val 去判断大小然后,将小的值放入新的链表
  • 值的一提的就是,链表这个可以通过引入伪头节点: 由于初始状态合并链表中无节点,因此循环第一轮时无法将节点添加到合并链表中。
  • 解决方案:初始化一个辅助节点 dum 作为合并链表的伪头节点,将各节点添加至dum 之后。
    cur = dum = ListNode(0)


  • 接下来要考虑的就是在遍历过程中的算法了
  • 首先确定一个整体思路,那就是通过赋值的方法,用while进行循环,且在每次逻辑判定后,使用L1 = L1.next, 这样可以减少L1的长度,且当L1.next为Null时结束遍历。
  • 当L1.val < L2.val 时,cur的后继节点为L1
  • 反之同理
  • 注意!!这里为什么是用后继结点进行赋值,因为用val不能改变dum的结构(长度)
  • 合并剩余尾部: 跳出时有两种情况,即 L1 为空 L2 为空。
  • 如果L1 为空 则cur.next = L2 ,反之同理
  • 代码如下
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 赋值两个新的链表,为ListNode
        dum = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            elif l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return dum.next

至于为什么dum 可以通过 cur赋值,这个是python变量问题

还有为什么返回dum.next是因为第一个节点是个伪节点,假的!


欢迎技术探讨