Leetcode Articles: Insert into a Cyclic Sorted List
2023-09-11 14:14:07 时间
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.
Solution:
Basically, you would have a loop that traverse the cyclic sorted list and find the point where you insert the value (Let’s assume the value being inserted called x). You would only need to consider the following three cases:
1. prev→val ≤ x ≤ current→val:
Insert between prev and current.
2. x is the maximum or minimum value in the list:
- Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.
3. Traverses back to the starting point:
- Insert before the starting point.
It's tricky to think of case 3:
Q: What if the list has only one value?A: Handled by case 3).
Q: What if the list is passed in as NULL?A: Then handle this special case by creating a new node pointing back to itself and return.
Q: What if the list contains all duplicates?A: Then it has been handled by case 3).
1 public class Solution { 2 public class ListNode { 3 int val; 4 ListNode next; 5 ListNode(int x) { 6 this.val = x; 7 this.next = this; 8 } 9 } 10 11 public ListNode rotateRight(ListNode start, int x) { 12 if (start == null) return new ListNode(x); 13 14 ListNode cur = start; 15 while (true) { 16 if (cur.val < cur.next.val) {//没有到拐点 17 if (x>=cur.val && x<=cur.next.val) { 18 insert(cur, x); 19 break; 20 } 21 else cur = cur.next; 22 } 23 else if (cur.val > cur.next.val) { //到了拐点 24 if (x>=cur.val || x<=cur.next.val) { 25 insert(cur, x); 26 break; 27 } 28 else cur = cur.next; 29 } 30 else { //cur.val == cur.next.val 31 if (cur.next == start) { 32 insert(cur, x); 33 break; 34 } 35 cur = cur.next; 36 } 37 } 38 return start; 39 } 40 41 public void insert(ListNode cur, int x) { 42 ListNode node = new ListNode(x); 43 node.next = cur.next; 44 cur.next = node; 45 } 46 }
相关文章
- Leetcode: 4Sum II
- Leetcode: Reverse Linked List
- Leetcode: Rotate List
- Leetcode: Palindrome Numbers
- LeetCode——Remove Duplicates from Sorted List II
- [LeetCode] Linked List Cycle II
- [LeetCode] Remove Nth Node From End of List
- [LeetCode] Word Ladder II
- [LeetCode] Longest Valid Parentheses
- leetcode第72场双周赛记录
- Reorder List @LeetCode
- 【LeetCode】76. Minimum Window Substring
- 【LeetCode】88. Merge Sorted Array (2 solutions)
- 【LeetCode】142. Linked List Cycle II (2 solutions)
- 待字闺中之快排单向链表;leetcode之Sort List
- [leetcode] Insertion Sort List(python)
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 1147. Longest Chunked Palindrome Decomposition 段式回文
- [LeetCode] 970. Powerful Integers 强力数字
- [LeetCode] 967. Numbers With Same Consecutive Differences 连续差相同的数字
- [LeetCode] Shortest Completing Word 最短完整的单词
- [LeetCode] Self Dividing Numbers 自整除数字
- [LeetCode] 296. Best Meeting Point 最佳开会地点
- [LeetCode] 257. Binary Tree Paths 二叉树路径
- [LeetCode] 234. Palindrome Linked List 回文链表
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二
- leetcode 695. Max Area of Island 岛屿的最大面积(中等)
- leetcode 142. Linked List Cycle II 环形链表 II
- leetcode算法53.最大子数组和