链表常见算法

判断链表是否有环

双指针算法：设置一个快指针（每次前进两步），一个慢指针（每次前进一步），若快指针遇到空则没有环，若快指针等于慢指针则成环。
返回链表入环的第一个节点：当两个指针相遇后，将慢指针设置成头指针，与快指针并行前进（相同速度），两指针再次相遇处即为入环点。(快指针总是比慢指针多走一倍的路程)

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

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

判断链表相交

双指针算法：两个指针a，b分别指向各自的头节点，当一个指针走到头后，从另一个链表的头节点继续遍历，两个指针的相遇点就是相交点。

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	if (headA == NULL || headB == NULL)
		return NULL;
	ListNode* pa = headA;
	ListNode* pb = headB;
	while (pa != pb) {
		pa = pa == NULL ? headB : pa->next;
		pb = pb == NULL ? headA : pb->next;
	}
	return pa;
}

删除/寻找倒数第k个节点

双指针，一个指针先移动k步，后面两个指针再一起移动，当第一个指针移动到空节点时，后一个指针就是第k个节点。

ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    for (int i = 0; i < k; i++) {
        p1 = p1 -> next;
    }
    ListNode* p2 = head;
    while (p1 != nullptr) {
        p2 = p2 -> next;
        p1 = p1 -> next;
    }
    return p2;
}

若是删除则需注意内存管理，可以先开一个虚拟头节点.

ListNode* removeNthFromEnd(ListNode* head, int n) {
	//虚拟头节点，指向真正的头节点
	ListNode* tmp = new ListNode(0,head);
	ListNode* fast = head;
	ListNode* slow = tmp;
	//先移动k步
	for(int i=0;i<n;i++) fast=fast->next;
	//一起移动，当fast指向空时结束
	while(fast)
	{
		fast=fast->next;
		slow=slow->next;
	}
	//此时slow->next指向要删除的节点
	ListNode* deletenode = slow->next;
	slow->next = slow->next->next;
	delete deletenode;
	//重新返回头指针，防止删除头指针元素的情况
	ListNode* newhead = tmp->next;
	delete tmp;
	return newhead;
}

有序合并两个有序链表

双指针，分别指向两个链表的开头，还有一个指针指向新链表。每次比较两个指针指向的值，较小者入新表，然后对应的指针向后移动。当其中一个指针移动到末尾时，将另外一个指针的剩余节点并入新链表。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	ListNode* p1=list1;
	ListNode* p2=list2;
	ListNode* now=new ListNode(0,nullptr);
	ListNode* p3=now;
	while(p1!=nullptr && p2!=nullptr)
	{
		//比较两个指针，较小者入。
		if(p1->val < p2->val)
		{
			p3->next = p1;
			p1 = p1->next;
		}
		else
		{
			p3->next = p2;
			p2 = p2->next;
		}
		p3 = p3->next;
	}
	//处理剩余节点
	if(p1!=nullptr)
	{
		p3->next = p1;
	}
	if(p2!=nullptr)
	{
		p3->next = p2;
	}
	Listnode* ret = now->next;
	delete now
	return ret;

有序合并k个链表

使用优先队列（最小二叉堆）实现快速得到最小值的节点。

ListNode* mergeKLists(vector<ListNode*>& lists) {
	//lambda函数自定义比较优先级
	auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val;};
	//优先队列(最小二叉堆的声明，存储类型，底层容器，比较函数)
	priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq(cmp);
	//虚拟头节点
	ListNode* newnode = new ListNode(0);
	ListNode* p = newnode;
	//所有链表的头节点入优先队列
	for(auto head:lists){
	//排除空表
		if(head==nullptr) continue;
		pq.push(head);
	}

	while(!pq.empty())
	{
		//每次取顶部节点入新链表(顶部即最小)
		ListNode* topnode = pq.top();
		pq.pop();
		p->next = topnode;
		//将顶部节点的后继入队列
		if(topnode->next != nullptr)
			pq.push(topnode->next);
		//更新指针
		p = p->next;
	}
	Listnode* ret = newnode->next;
	delete newnode;
	return ret;
}

分解链表

题意：
- 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
解法：
- 开两个新链表，一个存放小于x的节点，另一个存放大于等于x的节点，设一个指针从原链表头部开始遍历，依次比较后加入对应的新链表，最后将两个链表拼接起来。

ListNode* partition(ListNode* head, int x) {
	//开两个新链表
	ListNode* lex = new ListNode(0); //less than x
	ListNode* meqx = new ListNode(0); // more than or equal x
	ListNode* p = head; ListNode* p1=lex; ListNode* p2=meqx;
	while(p!=nullptr)
	{
		if(p->val < x)
		{
			p1->next = p;
			p1 = p1->next;
		}
		else
		{
			p2->next = p;
			p2 = p2->next;
		}
		//更新指针
		p=p->next;
	}
	//合并两个链表
	p1->next = meqx->next;
	//设置链表末尾，防止内存报错
	p2->next = nullptr;
	ListNode* ret = lex->next;
	delete lex;
	delete meqx;
	return ret;
}