[LeetCode]easy - Merge Two Sorted Lists - python

Problem Description:

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

题目链接

题目要求将两个非降序排列的链表 合并成一个非降序排列的链表。

思路一

生成一个新的空链表 接着对两个非降序排列的链表一步一步遍历 都从头开始遍历 比较指针所指元素的大小 小的元素往新链表里填 然后原本转向较小元素的指针往后移一位 指向较大元素的指针不动 再次比较指针所指元素大小 重复上面的过程。

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val 0, next None):
# self.val val
# self.next next
class Solution(object):
 def mergeTwoLists(self, l1, l2):
 :type l1: ListNode
 :type l2: ListNode
 :rtype: ListNode
 if not l1 or not l2:
 return l1 if l1 else l2
 p r ListNode(None)
 while l1 and l2:
 if l1.val l2.val:
 p.next l1
 l1 l1.next
 else:
 p.next l2
 l2 l2.next
 p p.next
 p.next l1 if l1 else l2
 return r.next
 

结果如下

思路二

递归实现 就不需要生成新链表了 直接改变两个链表中的连接关系。

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val 0, next None):
# self.val val
# self.next next
class Solution(object):
 def mergeTwoLists(self, l1, l2):
 :type l1: ListNode
 :type l2: ListNode
 :rtype: ListNode
 if not l1 or not l2:
 return l1 if l1 else l2
 if l1.val l2.val:
 l1.next self.mergeTwoLists(l1.next, l2)
 return l1
 else:
 l2.next self.mergeTwoLists(l1, l2.next)
 return l2
 

结果如下

Python的链表实现

不可以用head来遍历列表 否则会丢失列表的一些节点 可以使用和head相同类型的临时的指针变量 这个变量先初始化为链表结构的head指针 然后控制一个循环。