（一）使用快慢指针

（二）相遇的角度思考

141. Linked List Cycle

Linked List Cycle - LeetCode

相遇则且不为NULL则说明存在环

 bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && slow){
            slow = slow->next;
            fast = fast->next;
            if(fast)    fast = fast->next;
            if(slow==fast && fast!=NULL)    return true;
        }
        return false;
    }

142. Linked List Cycle II

Linked List Cycle II - LeetCode

推导思路：

 

 ListNode *detectCycle(ListNode *head) {
        
        ListNode* fast = head;
        ListNode* slow = head;
        while(slow && fast){
            slow = slow->next;
            fast= fast->next;
            if(fast)    fast = fast->next;
            
            if(slow==fast && slow!=NULL)//相遇——存在环
            {
                fast = head;
                break;
            }
        }
        while(slow && fast){
            if(slow==fast)  return slow;
            slow = slow->next;
            fast = fast->next;
           
        }
        return NULL;
    }

876. Middle of the Linked List

Middle of the Linked List - LeetCode

    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            fast = fast->next;
            if(fast) fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

160. Intersection of Two Linked Lists

Intersection of Two Linked Lists - LeetCode

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pAB = headA;
        ListNode* pBA = headB;
        while(pAB!=pBA){
            if(pAB==NULL)
                pAB = headB;
            else pAB = pAB->next;
            if(pBA==NULL)
                pBA = headA;
            else pBA = pBA->next;
        } 
        return pAB;
    }

（三）摘结点建新链

21. Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

设置哑结点不断摘到新链上

 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = (ListNode*)malloc(sizeof(ListNode));
        head->next = NULL;
        ListNode* r = head;
        while(list1 && list2){
            if(list1->val < list2->val){
                r->next = list1;
                list1 = list1->next;
            }
            else{
                r->next = list2;
                list2 = list2->next;
            }
            r = r->next;
        }
        while(list1){
           r->next = list1;
           list1 = list1->next;
           r = r->next;
        }    
        while(list2){
           r->next = list2;
           list2 = list2->next;
           r = r->next;
            
        }    
        r = head;
        head = head->next;
        free(r);
        return head;
    }

23. Merge k Sorted Lists

Merge k Sorted Lists - LeetCode

k个元素比较大小的思路：使用二叉堆-优先队列

关于优先队列的使用，参考：

ACM向：关于优先队列priority_queue自定义比较函数用法整理_一苇以航-CSDN博客_priority_queue 自定义比较

//priority_queue类默认为大根堆，需要修改比较器为小根堆

class Solution {
public:
    struct compare{//priority_queue类默认为大根堆，需要修改比较器为小根堆
        bool operator()(const ListNode* a,const ListNode* b){
        return a->val > b->val;
    }
};
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //实际运用：外排？
        //使用堆排序找到最小的结点作为第一个插入结点
        
        //建堆
        std::priority_queue<ListNode*,vector<ListNode*>,compare> pq;自定义一个比较类，为小根堆
        int n = lists.size();
        for(int i=0;i<n;i++){
            if(lists[i])    pq.push(lists[i]);
        }
        ListNode* head = new ListNode(0);//dumpy node
        head->next = NULL;
        ListNode* r = head;
        while(pq.size()){
            ListNode* cur = pq.top();
            pq.pop();
            r->next = cur;
            r = r->next;//尾插法加入新链中
            if(cur->next)   pq.push(cur->next);
        }
        return head->next;
    }
};

O（nlogn）time

另一思路：归并排序的思路，先两两合并