图和例子详细介绍Linked List

http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
//思路
/*
这道题就是要把所有的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插进去。
*/
class Solution {
public:
    /**
     * @param node a list node in the list
     * @param x an integer
     * @return the inserted new list node
     */
    ListNode* insert(ListNode* node, int x) {
        // Write your code here
        ListNode* newNode = new ListNode(x);
        //没有node的时候
        if (node == NULL) {
            newNode->next = newNode;
            return newNode;
        }
        //只有一个node的时候
        if (node->next == node) {
            node->next = newNode;
            newNode->next = node;
            return newNode;
        }
        ListNode* cur = node;
        ListNode* next = node->next;
        while (next != node) {
            // node < node->next &&  node <= x <= node->next
            if(cur->val <= next->val && (x >= cur->val && x <= next->val)) {
                break;
            // node > node->next && x >node or x < node->next
            } else if (cur->val >= next->val && (x >= cur->val && x <= next->val)) {
                break;
            } else {
            // continue next
            cur = next;
            next = next->next;
            }
        }
        //insert the newNode into linked list
        cur->next = newNode;
        newNode->next = next;
        return next;

    }
};