LeetCode 708 - Insert into a Cyclic Sorted List


http://www.cnblogs.com/grandyang/p/9981163.html
Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.
If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.
If the list is empty (i.e., given node is null), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.
The following example may help you understand the problem better:



In the figure above, there is a cyclic sorted list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list.



The new node should insert between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.
http://hehejun.blogspot.com/2018/09/leetcodeinsert-into-cyclic-sorted-list.html
思路很直观,注意edge case,大概有以下几种情况:

  1. list为空,我们新建node,并且将next指向自身
  2. 如果insertVal在某处节点curr满足,curr->val <= insertVal <= curr->next->val,insertVal插入curr之后
  3. 如果2中的情况没有出现,说明当前插入值是新的最大/最小值,我们需要在当前最大值对应的节点(有多个的话选最靠后的一个)之后插入
   Node* insert(Node* head, int insertVal) {
      if (!head)
      {
         Node* node = new Node(insertVal, nullptr);
         node->next = node;
         return node;
      }
      Node* curr = head, *maxNode = head;
      bool inserted = false;
      while(true)
      {
         if (curr->next->val < curr->val)
            maxNode = curr;
         if (curr->next->val >= insertVal && curr->val <= insertVal)
         {
            Node* node = new Node(insertVal, curr->next);
            curr->next = node;
            inserted = true;
            break;
         }
         curr = curr->next;
         if (curr == head)break;
      }
      //turning point from max to min
      if (!inserted)
      {
         Node* node = new Node(insertVal, maxNode->next);
         maxNode->next = node;
      }
      return head;
   }
https://yeqiuquan.blogspot.com/2017/04/lintcode-599-insert-into-cyclic-sorted.html
这道题就是要把所有的case都想清楚。
1:如果node就是null,需要造一个新的node,并且自己和自己连上。
除去以上的case,我们需要在这个链表里找到需要插入的点的位置。我们遍历链表,并且进行不同case的分析。
2:如果node.val < node.next.val,那么如果x在这里两个值当中,我们就可以把x插进去。
3:如果node.val > node.next.val,这说明现在我们在链表的环的最后一个节点。那么如果x比整个链表中最大的节点值node.val还大,或者比整个链表中最小的节点值node.next.val还小,那么x可以插在这两个当中。
4:如果node.val == node.next.val,那么我们还是要判断一下node是不是就是环的最后一个节点,以及node.next是不是环的头。如果是这样,我们可以把x插进去。
    public ListNode insert(ListNode node, int x) {
        if (node == null) {
            node = new ListNode(x);
            node.next = node;
            return node;
        }
        
        ListNode head = node;
        while (node != null && node.next != null) {
            if (node.val < node.next.val) {
                if (node.val <= x && x <= node.next.val) {
                    insertNode(node, x);
                    break;
                }
            }
            else if (node.val > node.next.val) {
                if (x > node.val || x < node.next.val) {
                    insertNode(node, x);
                    break;
                }
            }
            else { // node.val == node.next.val
                if (node.next == head) {
                    insertNode(node, x);
                    break;
                }
            }
            node = node.next;
        }
        
        return head;
    }
    
    public void insertNode(ListNode node, int x) {
        ListNode newNode = new ListNode(x);
        newNode.next = node.next;
        node.next = newNode;
    }



https://blog.csdn.net/sinat_32547403/article/details/78510434

  public ListNode insert(ListNode node, int x) {
    // write your code here
    ListNode n = new ListNode(x);
    if (node == null) {
      n.next = n;
      return n;
    }
    ListNode curr = node.next;
    ListNode prev = node;
    while (curr != node) {
      if (prev.val <= x && curr.val >= x) {
        break;
      }
      if (prev.val > curr.val && (prev.val < x || curr.val > x)) {
        break;
      }
      curr = curr.next;
      prev = prev.next;
    }
    prev.next = n;
    n.next = curr;
    return node;
  }



这道题让我们在循环有序的链表中插入结点,要求插入结点后,链表仍保持有序且循环。题目中强调了corner case的情况,就是当链表为空时,我们插入结点即要生成一个新的循环有序链表,那么我们可以先处理这个特殊情况,比较简单,就是新建一个结点,然后将next指针指向自己即可。好,下面来看给定的链表不为空的情况,最常见的情况就是要插入的结点值在两个有序结点值[a, b]之间,那么只要满足 a <= insertVal <= b 即可。由于是循环有序的链表,结点值不会一直上升,到某一个结点的时候,是最大值,但是下一个结点就是最小值了,就是题目中的例子,结点4到结点1的时候,就是下降了。那么在这个拐点的时候,插入值insertVal就会有两种特殊的情况,其大于等于最大值,或者小于等于最小值,比如插入值是5,或者0的时候,这两种情况都插入在结点4之后,可以放一起处理。而若其小于最大值,或者大于最小值,就是上面那种一般的情况,不会在这里处理,所以我们只要检测如果属于上面的两种情况之一,就break掉循环,进行插入结点处理即可
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            head = new Node(insertVal, NULL);
            head->next = head;
            return head;
        }
        Node *pre = head, *cur = pre->next;
        while (cur != head) {
            if (pre->val <= insertVal && cur->val >= insertVal) break;
            if (pre->val > cur->val && (pre->val <= insertVal || cur->val >= insertVal)) break;
            pre = cur;
            cur = cur->next;
        }
        pre->next = new Node(insertVal, cur);
        return head;
    }

https://segmentfault.com/a/1190000017139433
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node();
            head.val = insertVal;
            head.next = head;
            return head;
        }
        Node next = head.next, pre = head;
        while (next != head) {
            //insert in flat or rising range
            if (pre.val == insertVal || (pre.val < insertVal && insertVal < next.val)) {
                Node cur = new Node(insertVal, next);
                pre.next = cur;
                return head;
            }
            //insert in peak and falling range
            if (pre.val > next.val && (insertVal < next.val || insertVal > pre.val)) {
                Node cur = new Node(insertVal, next);
                pre.next = cur;
                return head;
            }
            
            pre = next;
            next = next.next;
        }
        //insert before head
        Node cur = new Node(insertVal, next);
        pre.next = cur;

        return head;
    }
https://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/
1) Linked List is empty:  
    a)  since new_node is the only node in CLL, make a self loop.      
          new_node->next = new_node;  
    b) change the head pointer to point to new node.
          *head_ref = new_node;
2) New node is to be inserted just before the head node:    
  (a) Find out the last node using a loop.
         while(current->next != *head_ref)
            current = current->next;
  (b) Change the next of last node. 
         current->next = new_node;
  (c) Change next of new node to point to head.
         new_node->next = *head_ref;
  (d) change the head pointer to point to new node.
         *head_ref = new_node;
3) New node is to be  inserted somewhere after the head: 
   (a) Locate the node after which new node is to be inserted.
         while ( current->next!= *head_ref && 
             current->next->data data)
         {   current = current->next;   }
   (b) Make next of new_node as next of the located pointer
         new_node->next = current->next;
   (c) Change the next of the located pointer
         current->next = new_node; 
void sortedInsert(Node new_node)
{
        Node current = head;
        // Case 1 of the above algo
        if (current == null)
        {
                new_node.next = new_node;
                head = new_node;
        }
        // Case 2 of the above algo
        else if (current.data >= new_node.data)
        {
                /* If value is smaller than head's value then
                 we need to change next of last node */
                while (current.next != head)
                        current = current.next;
                current.next = new_node;
                new_node.next = head;
                head = new_node;
        }
        // Case 3 of the above algo
        else
        {
                /* Locate the node before the point of insertion */
                while (current.next != head &&
                             current.next.data < new_node.data)
                        current = current.next;
                new_node.next = current.next;
                current.next = new_node;
        }
}

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts