链表

Remove Nth Node From End of List

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL) return head;
        ListNode new_head(0);
        new_head.next = head;
        ListNode* f = &new_head;
        ListNode* s = &new_head;
        while(f->next!=NULL){
            f = f->next;
            if (n<1){
                s = s->next;
            }
            n--;
        }
        ListNode *tmp = s->next;
        s->next = s->next->next;
        delete tmp;
        return new_head.next;

    }
};

Sort List

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* fast = head->next;
        ListNode* slow = head;
        while (fast!=NULL && fast->next!=NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = slow->next;
        slow->next =NULL;
        return merge(sortList(head),sortList(fast));

    }
    ListNode* merge(ListNode* l1, ListNode* l2){
        if (l1==NULL ) return l2;
        if (l2==NULL) return l1;
        ListNode r(0);
        ListNode* p = &r;
        while (l1!=NULL&&l2!=NULL){
            if (l1->val <= l2->val){
                p->next = l1;
                p = p->next;
                l1= l1->next;
            }else{
                p->next = l2;
                p = p->next;
                l2= l2->next;                
            }
        }
        if (l1 ==NULL) p->next = l2;
        if (l2  ==NULL) p->next = l1;
        return r.next;
    }
};

Reverse Linked List

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head ->next == NULL){
            return head;
        }
        ListNode* r = new ListNode(0);
        while (head  != NULL){
            ListNode* t = head;
            head = head->next;
            t->next = r->next;
            r->next = t;
        }
        r= r->next;
        return r;
    }
};

Remove Duplicates from Sorted List

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* r= head;
        while ( head->next != NULL){
            if (head->val == head->next->val){
                head->next = head->next->next;
            }else{
            head=head->next;
            }
        }
        return r;

    }
};