顺序遍历循环链表，求解《708. 循环有序列表的插入》和《剑指 Offer II 029. 排序的循环链表》
例题
708. 循环有序列表的插入
剑指 Offer II 029. 排序的循环链表
给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环非降序的。
给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，你可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），你需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
答案
顺序遍历
var insert = function(head, insertVal) {
let r = prev = head
while (head) {
if (insertVal >= prev.val && insertVal <= head.val ||
head.val < prev.val && (insertVal <= head.val || insertVal >= prev.val)) break
prev = head
head = head.next
if (head === r) break
}
if (prev) prev.next = new Node(insertVal, prev.next)
else {
r = new Node(insertVal)
r.next = r
}
return r
};function insert(head: Node | null, insertVal: number): Node | null {
let r = head, prev = head
while (head) {
if (insertVal >= prev.val && insertVal <= head.val ||
head.val < prev.val && (insertVal >= prev.val || insertVal <= head.val)) break
prev = head
head = head.next
if (head === r) break
}
if (prev) prev.next = new Node(insertVal, prev.next)
else {
r = new Node(insertVal)
r.next = r
}
return r
}func insert(aNode *Node, x int) *Node {
r, prev := aNode, aNode
for aNode != nil {
if x >= prev.Val && x <= aNode.Val ||
aNode.Val < prev.Val && (x >= prev.Val || x <= aNode.Val) {
break
}
prev = aNode
aNode = aNode.Next
if aNode == r {
break
}
}
if prev != nil {
prev.Next = &Node{x, prev.Next}
} else {
r = &Node{x, nil}
r.Next = r
}
return r
}class Solution {
function insert($head, $insertVal) {
$r = $head;
$prev = $head;
while ($head) {
if ($insertVal >= $prev->val && $insertVal <= $head->val ||
$head->val < $prev->val && ($insertVal >= $prev->val || $insertVal <= $head->val)
) break;
$prev = $head;
$head = $head->next;
if ($head === $r) break;
}
if ($prev) {
$t = new Node($insertVal);
$t->next = $prev->next;
$prev->next = $t;
} else {
$r = new Node($insertVal);
$r->next = $r;
}
return $r;
}
}class Solution {
public Node insert(Node head, int insertVal) {
Node r = head, prev = head;
while (head != null) {
if (insertVal >= prev.val && insertVal <= head.val ||
head.val < prev.val && (insertVal <= head.val || insertVal >= prev.val)) break;
prev = head;
head = head.next;
if (head == r) break;
}
if (prev != null) prev.next = new Node(insertVal, prev.next);
else {
r = new Node(insertVal);
r.next = r;
}
return r;
}
}class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
r, prev = head, head
while head:
if insertVal >= prev.val and insertVal <= head.val or head.val < prev.val and (insertVal >= prev.val or insertVal <= head.val): break
prev = head
head = head.next
if head == r: break
if prev: prev.next = Node(insertVal, prev.next)
else:
r = Node(insertVal)
r.next = r
return rstruct Node* insert(struct Node* head, int insertVal) {
struct Node *r = head, *prev = head;
while (head) {
if (insertVal >= prev->val && insertVal <= head->val ||
head->val < prev->val && (insertVal >= prev->val || insertVal <= head->val)) break;
prev = head;
head = head->next;
if (head == r) break;
}
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->val = insertVal;
if (prev) {
node->next = prev->next;
prev->next = node;
} else {
node->next = node;
r = node;
}
return r;
}class Solution {
public:
Node* insert(Node* head, int insertVal) {
Node *r = head, *prev = head;
while (head) {
if (insertVal >= prev->val && insertVal <= head->val ||
head->val < prev->val && (insertVal >= prev->val || insertVal <= head->val)) break;
prev = head;
head = head->next;
if (head == r) break;
}
if (prev) prev->next = new Node(insertVal, prev->next);
else {
r = new Node(insertVal);
r->next = r;
}
return r;
}
};public class Solution {
public Node Insert(Node head, int insertVal) {
Node r = head, prev = head;
while (head != null) {
if (insertVal >= prev.val && insertVal <= head.val ||
head.val < prev.val && (insertVal >= prev.val || insertVal <= head.val)) break;
prev = head;
head = head.next;
if (head == r) break;
}
if (prev != null) prev.next = new Node(insertVal, prev.next);
else {
r = new Node(insertVal);
r.next = r;
}
return r;
}
}