725. Split Linked List in Parts

    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode*> nd(k, root);
        if(root == nullptr) return nd;
        ListNode* p = root;
        int N=0;
        while(p) {
            N++;
            p = p->next;
        }
        int n2 = N/k, n1 = n2+1;
        int k1 = N - n2*k, k2 = k - k1;
        p = root;
        for(int i=0; i<k; i++) {
            if(i<k1) {
                nd[i] = p;
                int j=0;
                while(j<n1-1) {
                    p=p->next;
                    j++;
                }
                ListNode* q = p;
                p = p->next;
                q->next = nullptr;
            }
            else {
                nd[i] = p;
                if(p==nullptr) continue;
                int j=0;
                while(j<n2-1) {
                    p=p->next;
                    j++;
                }
                ListNode* q = p;
                p = p->next;
                q->next = nullptr;
            }
        }
        return nd;
    }

445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/
Solution 1. Read the value to 2 vectors.
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1, v2;
        ListNode* ln, * res = nullptr;
        ln = l1;
        while(ln) {
            v1.push_back(ln->val);
            ln = ln->next;
        }
        ln = l2;
        while(ln) {
            v2.push_back(ln->val);
            ln = ln->next;
        }
        int NI = v1.size(), NJ = v2.size(), c = 0;
        for(int i=NI-1, j=NJ-1; i>=0||j>=0|| c; i--, j--, c/=10) {
            if(i>=0) c+=v1[i];
            if(j>=0) c+=v2[j];
            ln = new ListNode(c%10);
            ln->next = res;
            res = ln;
        }
        return res;
    }
Or use a stack:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1;
        stack<int> s2;
        ListNode* l = l1, * res=nullptr;
        while(l){
            s1.push(l->val);
            l = l->next;
        }
        l = l2;
        while(l) {
            s2.push(l->val);
            l = l->next;
        }
        l = nullptr;
        int c = 0;
        while(!s1.empty() || !s2.empty() || c) {
            if(!s1.empty()) {
                c += s1.top();
                s1.pop();
            }
            if(!s2.empty()) {
                c += s2.top();
                s2.pop();
            }
            l = new ListNode(c%10);
            l->next = res;
            res = l;
            c /= 10;
        }
        return res;
    }

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/
Solution 1. 
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* p = headA, *q = headB;
        while(p != q) {
            p = p? p->next : headB;
            q = q? q->next : headA;
        }
        return p;

    }
Solution 2. Counting the length of the lists.
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* p, *q;
        int na = 0, nb = 0, nd = 0;
        p = headA;
        while(p) {
            na++;
            p = p->next;
        }
        p = headB;
        while(p) {
            nb++;
            p = p->next;
        }
        if(na>nb) {
            p = headA;
            q = headB;
        }
        else {
            p = headB;
            q = headA;
        }
        nd = abs(na - nb);
        while(nd>0) {
            p = p->next;
            nd--;
        }
        while(p != q) {
            p = p->next;
            q = q->next;
        }
        return p;
    }

203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/description/
Solution 0. Iteration 1. use pointer to a pointer.
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        ListNode** pn = &head;
        while(*pn) {
            if((*pn)->val == val) {
                *pn = (*pn)->next;
            }
            else {
                pn = &(*pn)->next;
            }
        }
        return head;
    }
Solution 1. Recursion 0
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        head->next = removeElements(head->next, val);
        ListNode* node = head;
        if(head->val == val) {
            head = head->next;
        }
        return head;
    }
Solution 1.1 Recursion 1
    void remove(ListNode*& node, int val) {
        if(!node) return;
        if(node->val == val) {
            node = node->next;
            remove(node, val);
        }
        else remove(node->next, val);
    }
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        remove(head, val);
        return head;
    }
Solution 2. Iteration 2
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;
        ListNode* node = head, *pre = head;
        while(node) {
            if(node->val == val) {
                if(node == head) {
                    head = head->next;
                    node = head;
                    pre = head;
                }
                else {
                    pre->next = node->next;
                    node = pre->next;
                }
            }
            else {
                pre = node;
                node = node->next;
            }
        }
        return head;
    }

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/
Solution 1. Use a recursive call to check the values. The call stack acts as a stack for the node values, which access the node values backwardly. At the same time, use a pointer p to access the node values forwardly. O(n) in space.
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        return check(head, p);
    }
    bool check(ListNode* node, ListNode*& p) {
        if(!node) return true;
        bool isNext = check(node->next,p) && (node->val == p->val);
        p = p->next;
        return isNext;
    }
Solution 2. O(1) space?
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head, * fast = head, *p;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverseList(slow->next);
        slow->next = fast;
        p = head;
        while(fast) {
            if(p->val != fast->val) return false;
            p = p->next;
            fast = fast->next;
        }
        slow->next = reverseList(slow->next);
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* hd = nullptr, * next;
        while(head) {
            next = head->next;
            head->next = hd;
            hd = head;
            head = next;
        }
        return hd;
    }

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/
Solution 0. Use a dummy node as the head. (9 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(INT_MIN);
        ListNode* tail = &head;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1? l1:l2;
        return head.next;
    }
Solution 1.0 Recursion. Slow but simple. (19 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
Solution 1.1  (12 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        ListNode* head = l1;
        ListNode* p;
        while(true) {
            while(l1->next && l1->next->val <= l2->val) l1 = l1->next;
            p = l1;
            l1 = l1->next;
            p->next = l2;
            if(!l1) return head;
            while(l2->next && l2->next->val <= l1->val) l2 = l2->next;
            p = l2;
            l2 = l2->next;
            p->next = l1;
            if(!l2) return head;
        }
    }

206. Reverse Linked List

Solution 1. Iterative method
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* node = head;
        while(node){
            head = node;
            node = node->next;
            head->next = prev;
            prev = head;
        }
        return head;

    }
Solution 2. Recursion
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return node;

    }
Solution 2. With the help of a stack
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;
        ListNode* node = head;
        while(node){
            st.push(node);
            node = node->next;
        }
        if(head) {
            head = st.top();
            node = head;
            st.pop();
        }
        while(!st.empty()) {
            node->next = st.top();
            st.pop();
            node = node->next;
        }
        if(node) node->next = nullptr;
        return head;
    }