面试常考链表问题

反转链表 + 反转部分链表

ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode * pre = dummy;
        for(int i = 1;i<m;i++){//注意下标从1开始
            head = head->next;
            pre = pre->next;
        }
        ListNode *father = pre;
        ListNode *cur = head;
        for(int i = m;i<=n;i++){//两侧都是闭区间
            auto tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        father->next = pre;
        head->next = cur;
        //pre是第一个节点
        return dummy->next;


    }

倒数第k个节点 + 中间的元素

快慢针解决
1.快针先走k步
2.快针每次走两步

链表中的环，是否有环，环的长度

快针每次走两步可解，关键是证明：
非环部分长a,环长b
慢针走到环入口时候,快针走了2a步，慢针走了a步，快针走了2a步，快针在环内的步数a，
慢针走了x步时候，快针步数为2x+a
2x+a)%a == 0的时候，两者相遇

环的长度为 再一次相遇时候，慢针移动步数

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

合并链表-k路归并

优先队列，定义节点的比较方法

#include<vector>
#include<queue>
using namespace std;

class Solution {
public:
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(nullptr) {}

    };
    struct  cmp
    {
        bool operator()(ListNode*a,ListNode*b){
            return a->val>b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size()==0)
        {
            return nullptr;
        }


        priority_queue<ListNode*,vector<ListNode*>,cmp> q;
        for(auto node:lists){
            if(node)q.push(node);
        }
        ListNode * res = new ListNode(-1);
        ListNode * head = res;
        while(!q.empty()){
            ListNode* next = q.top();
            q.pop();

            if(next->next){
                q.push(next->next);
            }
            head->next = next;
            head = head->next;
        }
        return res->next;
    }
};