Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. Return the inserted new node.
Notice
3->5->1is a cyclic list, so3is next node of1.
3->5->1is same with5->1->3
Example
Given a list, and insert a value4:
3->5->1
Return5->1->3->4
几种情况
1) Linked List is empty:
2) New node is to be inserted just before the head node:
3) New node is to be inserted somewhere after the head:
4) Linked List 只有一个node
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
# @param {ListNode} node a list node in the list
# @param {int} x an integer
# @return {ListNode} the inserted new list node
def insert(self, node, x):
# Write your code here
# case1: linkedlist is empty
if not node:
node = ListNode(x)
node.next = node
return node
prev = None
p = node
newNode = ListNode(x)
while True:
prev = p
p=p.next
# case2:x值在pre和p中间
if newNode.val >= prev.val and newNode.val <= p.val:
break
# case3: x值在head node前边，也就是pre>p的时候
if (prev.val > p.val) and (newNode.val >= prev.val or newNode.val <= p.val):
break
# case4: 如果linkedlist只有一个node的情况
if p is node:
break
prev.next = newNode
newNode.next = p
return newNode