输入：head = 1->4->6->8->null, val = 5
输出：1->4->5->6->8->null
样例 2：
输入：head = 1->null, val = 2
输出：1->2->null 第一个版本:
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The head of linked list.
@param val: An integer.
@return: The head of new linked list.
"""
def insertNode(self, head, val):
# write your code here
new_node = ListNode(val)
#边界情况
if not head: return None
if head.val >= val:
new_node.next = head
return new_node
p = head
while p.next:
#如果在中间的话，则直接返回
if val > p.val and val <= p.next.val:
new_node.next = p.next
p.next = new_node
return head
else:
p = p.next
else:
#如果不在中间
p.next = new_node
return head
第二个版本:
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The head of linked list.
@param val: An integer.
@return: The head of new linked list.
"""
def insertNode(self, head, val):
# write your code here
#一直到val < p.next.val 的时候退出
dummy = ListNode(0)
dummy.next = head
p = dummy
while p.next and val < p.next.val:
p = p.next
#开始拼接
new_node = ListNode(val, p.next)
p.next = new_node
return head
