代码随想录算法训练营第33期day04:第二章 链表 part02

24. 两两交换链表中的节点 10分05

        给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

示例 2：

输入：head = []

输出：[]

示例 3：

输入：head = [1]

输出：[1]

以图表文

这是群里一个大佬画的图，非常清晰，比我画的糊糊好太多，一起和膜拜大佬吧！！链接在这里 =>

ListNode* swapPairs(ListNode* head) {
	
	ListNode* vitualHead = new ListNode(0);		// 设置虚拟头节点
	vitualHead->next = head;	
	
	ListNode* p = vitualHead;
	while (p->next && p->next->next) {
		ListNode* temp1 = p->next->next->next;
		ListNode* temp2 = p->next;
		p->next = p->next->next;				
		p->next->next = temp2;					
		temp2->next = temp1;					
		p = p->next->next;						
	}
	return vitualHead->next;
}

收获：一图胜千言！！！！！！！！！！！！

19. 删除链表的倒数第 N 个结点 11 分 06 秒

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1

输出：[]

示例 3：

输入：head = [1,2], n = 1

输出：[1]

快慢指针

        利用快慢指针。初始时，快慢指针指向同一个位置，快指针先走 n 个位置，然后快慢指针一起走，当快指针走到链表尾时，慢指针的下一个就是要删除的结点。(不理解，可以自己画图模拟）

ListNode* removeNthFromEnd(ListNode* head, int n) {
	

	ListNode* vitualhead = new ListNode(0);
	vitualhead->next = head;

	ListNode* slow = vitualhead->next;
	ListNode* fast = vitualhead->next;
	int step = 0;
	while (fast&&fast->next) {
		if (step < n) {						// 快指针先走
			fast = fast->next; 
			++step;
		}
		else {								// 快慢指针一起走
			fast = fast->next;
			slow = slow->next;
		}
	}
	slow->next = slow->next->next;
	return head;
}

收获：双指针--快慢指针经验+1

面试题 02.07. 链表相交  

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。

在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。

在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。

由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

这两个链表不相交，因此返回 null 。

快慢指针

        快慢指针，快指针先走两链表相差的长度，然后两链表一起走，最后快慢指针指向的同一个结点就为相交结点。

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {

    if (headA == headB) return headB;

    // ①获取链表长度
    int lenA = 0;
    int lenB = 0;
    ListNode* pa = headA;
    ListNode* pb = headB;
    while (pa) {
        ++lenA;
        pa = pa->next;
    }
    while (pb) {
        ++lenB;
        pb = pb->next;
    }
    pa = headA;
    pb = headB;

    // ②长表先走
    if (lenA >= lenB) {
        int gap = lenA - lenB;
        while (gap--)pa = pa->next;
    }
    else {
        int gap= lenB - lenA;
        while (gap--)pb = pb->next;
    }
    // ③一起走
    while (pa && pb) {
        if (pa == pb) return pa; // 头结点也存储数据
        pa = pa->next;
        pb = pb->next;
    }
    return NULL;
}

收获：快慢指针经验+1

142. 环形链表 II  

这道题之前写过题解 看这里