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

发布时间:2024年01月21日

两两交换链表中的节点

Alt
两两交换节点,思路如下:
Alt
这样三步操作就实现了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个节点

Alt
也是使用双指针,添加虚拟节点 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;
	}
};

链表相交

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

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

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

  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
    所以再次使用双指针法,一个指针从头节点出发,另一个指针从相遇节点出发,两者相遇时就是入口节点。
    Alt
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;
	}
};
文章来源:https://blog.csdn.net/qq_44173169/article/details/135723379
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。