Day4

1.链表的题目，要在草稿纸上模拟清晰后就简单了

2.双指针更加灵活的应用。

3.环形链表多练习。

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

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* _dummyHead = new ListNode(0); //虚拟头结点_dummyHead -> next = head;ListNode* cur = head;ListNode* pre = _dummyHead;ListNode* tmp;while(cur != NULL && cur -> next != NULL){tmp = cur -> next -> next;//三个步骤pre -> next = cur -> next; cur -> next -> next = cur;cur -> next = tmp;//更新值pre = cur;cur = tmp;}ListNode* result = _dummyHead->next;delete _dummyHead;return result;}
};

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

直接法：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {//直接法,需要两次遍历ListNode* _hummyHead = new ListNode(0); //虚拟头结点_hummyHead -> next = head;ListNode* tmp = nullptr, *cur = _hummyHead; int count = 0; //记录节点个数if(cur -> next == NULL) return head;while(cur -> next != NULL){cur = cur -> next;count ++;}cur = _hummyHead;int m = count - n;//移动到要删除的节点的前一个位置while(m--){cur = cur -> next;}//删除操作if(cur -> next -> next != nullptr) tmp = cur -> next ->next;delete cur -> next;cur -> next = tmp;return _hummyHead -> next;}
};

第一次写，没有加“if(cur -> next == NULL) return head;”这句，程序一直报错，在这里我debug了很久。

要注意，cur -> next为nullptr的话，cur -> next -> next 就是非法的。

双指针法

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {//快慢指针，只用遍历一遍就可以删除节点ListNode *_hummyHead = new ListNode(0);_hummyHead -> next = head;ListNode *slow = _hummyHead, *fast = _hummyHead;//先正常写，然后判断边界情况while (n --){fast = fast -> next;}while(fast -> next != nullptr){slow = slow -> next;fast = fast -> next;}//删除节点ListNode *tmp = slow -> next;slow -> next = tmp -> next;delete tmp;return _hummyHead -> next;}
};

面试题 02.07. 链表相交

有点类似模拟题，思路清晰后挺简单的。

题目示例里面提到的，“题目条件如果两个链表相交则不能为 0”，意思是，0代表了NULL。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//相交的节点指地址是相同的，值相同的节点不一定地址相同ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB =0;while(curA != NULL){lenA ++;curA = curA -> next;}while(curB != NULL){lenB ++;curB = curB -> next;}curA = headA;curB = headB;//让curA成为最长链表的头if(lenA < lenB){swap(lenA, lenB);swap(curA, curB);}int gap = lenA - lenB;//让两表对齐while(gap --){curA = curA -> next;}while(curA != curB && curA != nullptr){curA = curA -> next;curB = curB -> next;}return curA;}
};

142.环形链表II

1.如何判断链表有环？

快慢指针相遇

2.假如慢指针每次移动一步，快指针每次移动两步，会不会存在这样的一个情况，即快慢指针永远无法相遇？

可以这样来看，慢指针相对于快指针静止，快指针每次相对移动一步来遇到慢指针，所以不存在永远无法相遇的情况。

3.如何判断快慢指针一定会相遇？

假如快指针每次移动5步，慢指针每次移动2步，以3步为单位的相对移动。

本质上是看以3步为单位的移动，是否一定能遍历环上的所有节点

所以只有当环长L不是3的倍数时才能相遇

4.环的入口怎么找？

快慢指针的运动如下图所示：

假设快慢指针在环中的某一点相遇，设：

①slow = x + y

（而不是 slow = x+y+n(y+z)，因为慢指针被快指针追上的时候，慢指针一定在走第一圈)

②fast = x + y + n(y+z)

因为fast = 2 * slow

有等式： 2 * (x + y) = x + y + n(y +z)

得到：x = n(y + z) - y，整理得：③x = (n - 1)(y + z) + z，其中n ≥ 1

由③式可知，让慢指针1和慢指针2分别从起点和相遇点出发，他们总会在环的入口相遇，这样就找到了环的入口。

5.慢指针被快指针追上的时候，为什么一定是在慢指针走第一圈的时候？

假设快指针已经走了3圈，把环铺开，如下图，慢指针没转完一圈，一定就被快指针追上了。

以下是我ac的代码，做的多余判断太多了，建议去看一下网站上的代码。

class Solution {
public:ListNode *detectCycle(ListNode *head) {//判断是否有环//记得考虑一下只有一个节点的情况和没有节点的情况ListNode* slow = head, *fast = head;if(head == nullptr || head->next == NULL) return NULL;while(fast != nullptr && fast->next != NULL){slow = slow -> next;fast = fast -> next -> next;if(slow == fast) break;}if(fast == nullptr|| fast->next == NULL) return NULL;//如果有环，返回入环的第一个节点ListNode *cur = head;while(cur != slow){slow = slow -> next;cur = cur -> next;}return cur;}
};

以下是我第一次写的报错的代码，刚开始就让快指针走了两步，导致表达式发生变化，所以报错，代码一定要严格按照表达式来。

class Solution {
public:ListNode *detectCycle(ListNode *head) {//判断是否有环//特殊判断一下只有一个节点的情况和没有节点的情况if(head == NULL && head -> next == NULL) return NULL;ListNode* slow = head, *fast = head -> next -> next;while(fast != nullptr && slow != fast){slow = slow -> next;fast = fast -> next -> next;}if(fast == nullptr) return NULL;//如果有环，返回入环的第一个节点ListNode *cur = head;while(cur != slow){slow = slow -> next;cur = cur -> next;}return cur;}
};