代码随想录算法训练营第四天|24、19、面试题 02.07、142、92（寄了）

Leecode24. 两两交换链表中的节点

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

其实这道题的思路和203比较相似，因为若是不设置虚拟头结点的话，处理头结点的方式和处理非头结点的方式会不一样，所以还是设置虚拟头结点

其实思路也是比较简单的，但是链表问题难就难在：有很多的指针都指向同一位置，牵一发而动全身，更改链表的指针需要非常的细心和谨慎

画图演示过程：

1. 我们从虚拟头结点开始操作，三步之后可以交换相邻两结点
2. 第二轮其实交换的是3和4，如同交换2和1的时候需要虚拟头结点一样，交换3和4的时候需要3之前的元素1，所以每次循环后需要将此次循环的“头结点”向前移动两次（例如交换3和4的时候操作的是1而不是dummy_head）
3. 但是循环也是有条件的， 每次交换两个元素，肯定需要保证循环时的“头结点”后有两个元素存在呀，就拿第一次交换举例，必须满足：v->next!=NULL及v->next->next!=NULL才可以开始循环
4. 循环开始之前定义的dummy_head是用来返回head的，循环中需要另外定义一个cur指针，此指针是随着循环进行而移动的

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 其实就是相邻节点的指针交换，设计一个虚拟头结点就很方便
        // 首先要明白只有一个节点或者没有节点的情况一定是非法的
        // 直接返回就可
        if (head == NULL || head->next == NULL) return head;

        ListNode *dummy_head = new ListNode(0);
        // 做一次循环判断一次，每次操作至少都需要两个元素
        // 第一次参与到循环中的最前面的节点是虚拟头结点，循环结束之后变成dummy—>next->next
        // 我们在循环结束就将dummy变成dummy->next->next，然后while中判断,若dummy->next!=NULL(两个元素的情况)且dummy->next->next!=NULL再进行循环
        dummy_head->next = head;
        // 应该定义一个循环变量，dummy_head的值肯定是不可以变的，但是在循环中必需有一个不断改变的“头指针”
        ListNode *cur = dummy_head;
        while (1) // 估计是被一起改变了
        {
            ListNode *temp1 = cur->next; // temp1指向1
            cur->next = cur->next->next; // dummy_head->next指向2

            ListNode *temp2 = temp1->next; // temp2指向2
            ListNode *temp3 = temp2->next;
            temp2->next = temp1; // temp2的next指向1

            ListNode *temp4 = cur->next->next;
            temp4->next = temp3;
            // 02134
            // 应该在这里退出，而不是在循环开始的时候退出  
            cur = cur->next->next;
            if (cur->next == NULL || cur->next->next == NULL) break;
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

快慢指针，很容易就可以A，但是要想清楚逻辑

看图：

开始的时候我们定义快慢指针，假设经过移动后快指针指向NULL而慢指针指向的是3（此时n = 2，所以慢指针指向的是要删除元素的前面一个元素），但是为什么要指向欲删除元素的前面一个元素呢？因为删除此元素后要连接前面元素和后面元素，如果不是从前面开始删除的话会找不到目标元素前面的元素

往前倒推，开始的时候让p指向的是虚拟头结点dummy_head，q指向的是后面n+1个节点，然后让两个指针一起向后移动，若q == NULL，那么此时p已经移动到了目标元素的前面位置，删除即可

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// 首先生成两个节点，都指向head，也就是head之前的空节点
		// 然后另其中一个节点向前移动n+1次
		ListNode* vir = new ListNode(0);
        vir -> next = head;
        ListNode *p = vir;
        ListNode *q = vir;
		for (int i = 0; i < n + 1; i++) q = q->next;
		
		// 然后令q和p一起移动，直到q为空为止
		while (q != NULL)
		{
			p = p->next;
			q = q->next;
		}
		ListNode * tar = p->next;
		p->next = p->next->next;
		delete tar;

        ListNode * res = vir->next;
        delete vir;
		return res;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

面试题 02.07. 链表相交

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

其实这类思维题，就是观察并且理解题目的特点，对症下药

规律就是两个相交的链表，在相交之后的长度一定都是相等的！

那么，对于较长的链表B而言，判断B中比A多出来的前一个的元素，是完全没有意义的，他们只会在最后三个元素相交（或者根本就不相交）

所以，我们可以先让两个链表底部对齐，并且从相对较短的链表的第一个元素开始判断，判断和其位置相同的另一个链表中的指针是不是和它指向同一个位置，若不是，二者同时向前挪动一个位置···

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // 开始的时候先计算链表A和链表B的长度
        ListNode *curA = headA;
        ListNode *curB = headB;
        int len_A = 0,len_B = 0;
        // 先得到二者的长度
        while(curA != NULL) {curA = curA ->next;len_A++;}
        while(curB != NULL) {curB = curB ->next;len_B++;}
		
        // 为了方便默认A的长度大于B的长度，如果不是，就把较长的B赋给A（AB交换，指针也一起）
        curA = headA;
        curB = headB;
        if(len_B > len_A){swap(len_A,len_B);swap(curA,curB);}

        // 将A和B移动到相同的索引，其实只要移动A就OK
        int len = (len_A - len_B);
        while(len--) {curA = curA->next;}

        while(curA!=NULL) 
        {
            if(curA == curB) 
            return curA;curA = curA->next;curB = curB->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Leecode142.环形链表II

链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

还是快慢指针，理解了思路就很容易A

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 开始的时候分别定义快指针和慢指针，
        // 其中快指针每次走两步，慢指针每次走一步，循环的判断条件是fast!=NULL及fast->next!=NULL
        // 直至两个指针相遇，再次进入一个循环
        // 在第二个循环开始的时候定义一个指针从头开始遍历，另外一个指针就是接着慢指针往前走
        // 在这个循环中相遇的点，就是环的入口处，此时直接返回就OK

        // 否则直接返回null
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!= NULL && fast->next!= NULL) // 虽然循环里面有fast->next->next，但是只要保证fast和fast->next!=NULL即可，也就是说不出现空指针的next就可以
        {
            slow = slow ->next;
            fast = fast ->next ->next;
            if(slow == fast)
            {
                ListNode *start = head;
                while(start!=slow)
                {
                    start = start->next;
                    slow = slow->next;
                }
                return start;
            }
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Leecode92. 反转链表 II(寄了)

主要是记录错点，本来想把反转链表①中的结论直接套到这里面来，但是有大坑！坑死我了！

其中反转链表①中的核心代码如下：(双指针)

while(now != NULL) // 改成beh->next就报错
        {
            ListNode * temp = now->next; // temp 现在是5，然后now是4，pree是3

            now -> next = pree; 

            pree = now;
            now = temp;
        }
1
2
3
4
5
6
7
8
9

循环中的NULL及其关键，改成非NULL的其他有效指针就很容易错，比如将其改为“now!=beh->next”，那么非常amazing的事情就会发生在循环中——当now == beh的时候，对now的操作会连beh一起改变，这样死都不知道是怎么死的（我真的，被哭死）

指针真的太危险了