Linked List Cycle

对链表反序： while(p) { q=p->next; p->next=f; f=p;p=q;}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *p=head,*q,*f=NULL;
        while(p){//对链表反序，如果p回到起点，则有环
            q=p->next;
            p->next=f;
            f=p;p=q;
            if(p==head) return true;//有环
        }
        return false;//沒有环，p到了NULL
    }
};

合并有序链表

用优先队列（小顶堆）

class Solution {
public:
    struct cmp{
        bool operator () ( const pair<int, int> &a, const pair<int, int > &b){
            return a.first >= b.first;
        }
    }cc;
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> que;
        for(int i=0; i<lists.size(); i++) if(lists[i]) 
            que.push(pair<int, int>(lists[i]->val, i));
        
        ListNode *head =NULL, *tail =NULL;
        while(!que.empty()){
            pair<int, int> t = que.top(); que.pop();
            int i = t.second;
            if(!head) head = lists[i];
            else tail -> next = lists[i];
            tail = lists[i];
            lists[i] = lists[i]->next;
            if(lists[i]) 
                que.push(pair<int, int>(lists[i]->val, i));
        }
        
        if(tail) tail->next = NULL;
        
        return head;
    }
};