代码随想录算法训练营第四天 | 24.两两交换链表中的节点 19.删除链表的倒数第N个节点 160.链表相交 142.环形链表II

两两交换链表中的节点

两两交换节点，思路如下：

这样三步操作就实现了2和1两个节点的交换，循环操作，每一次循环移动到交换好的最后一个节点。循环的截止条件就是没有节点剩余了，或者只剩一个节点。翻转链表的精髓还是在于暂存原链表中的 next 指针，然后再改变 next 指针的指向。

class Solution{
public:
	ListNode* swapPairs(ListNode* head){
		ListNode* dummy = new ListNode();
		dummy->next = head;
		ListNode* cur = dummy;
		// 循环终止条件：不再剩余节点，或只剩下一个节点
		while(cur->next != NULL && cur->next->next != NULL){
			ListNode* tmp = cur->next;  // 暂存要改变的指针
			ListNode* tmp1 = cur->next->next->next;

			cur->next = cur->next->next;  // 步骤一
			cur->next->next = tmp; // 步骤二
			cur->next->next->next = tmp1;  // 步骤三
			cur = cur->next->next;  // 移动到翻转好的最后一个节点
		}
		return dummy->next;
	}
};

删除链表的倒数第N个节点

也是使用双指针，添加虚拟节点 dummy，初始状态 fast 和 slow 均在 dummy，fast 指针要先走 n+1 步，因为我们要让 slow 最终停在要删除节点的前一个。

class Solution{
public:
	ListNode* removeNthFromEnd(ListNode* head, int n){
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		ListNode* fast = dummy;
		ListNode* slow = dummy;
		while(n-- && fast != NULL){
			fast = fast->next;
		}
		fast = fast->next;  // 多走一步，到n+1步
		while(fast != NULL){  // fast抵达NULL，slow抵达要删除节点的前一个节点
			slow = slow->next;
			fast = fast->next;
		}
		slow->next = slow->next->next;
		return dummy->next;
	}
};

链表相交

注意一定要判断指针是否相等，不要简单地判断元素值。具体的思路如下图所示，使两个链表的末尾对齐，开始逐一比较 curA 和 curB。指针相等了就找到了相交节点。

class Solution{
public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB){
		ListNode* curA = headA;
		int lenA = 0;
		while(curA){
			curA = curA->next;
			lenA++;
		}
		ListNode* curB = headB;
		int lenB = 0;
		while(curB){
			curB = curB->next;
			lenB++;
		}
		curA = headA;
		curB = headB;
		if(lenB > lenA){  // 保证A链表的长度更长
			swap(lenA, lenB);
			swap(curA, curB);
		}
		int gap = lenA - lenB;
		while(gap--){  // 使得A链表和B链表的末尾对齐
			curA = curA->next;
		}
		while(curA != NULL){
			if(curA == curB)  return curA;
			curA = curA->next;
			curB = curB->next;
		}
		return NULL;
	}
};

环形链表II

这道题需要两步走，首先判断链表中是否有环，再找环的进入节点。

1. 判断是否有环。用两个快慢指针遍历链表，如果两个指针能相遇，说明有环。类比跑步跑圈，跑的快的人一定能扣圈。
2. 找到环的入口节点。fast 指针一次走两步，slow 指针一次走一步。fast 指针走的路程总长度是x + y + n1(y + z)，n1 为 fast 指针在环内走的圈数，至少走了一圈（>=1）。此时 slow 指针走的距离为 x + y + n2(y + z)，n2 >= 0。
   2 * (x + y + n2(y + z)) = x + y + n1(y + z)
x + y + 2 * n2(y + z) = n1(y + z)
x + y = (n1 - 2 * n2)(y + z)
x = (n1 - 2 * n2 - 1)(y + z) + z
   所以再次使用双指针法，一个指针从头节点出发，另一个指针从相遇节点出发，两者相遇时就是入口节点。
   

class Solution{
public:
	ListNode* detectCycle(ListNode* head){
		ListNode* fast = head;
		ListNode* slow = head;
		while(fast != NULL && fast->next != NULL){  // 如果fast节点空或者没有后继节点
			fast = fast->next->next;
			slow = slow->next;
			if(fast == slow){  // 快慢指针相遇，证明有环
				while(fast != head){  // 寻找入环节点。有环了肯定可以找到
					fast = fast->next;
					head = head->next;
				}
				return head;
			}
		}
		return NULL;
	}
};