代码随想录训练营第四天——两两交换链表中的节点，删除链表倒数第N个节点，链表相交，环形链表2_dummyhead = listnode(none, head) cur = dummyhead,为

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

题目链接：两两交换链表中的节点
本题使用虚拟头结点处理，否则每次针对头结点需要单独处理。
交换相邻两个元素了，初始时，cur指向虚拟头结点，然后进行如下三步：

交换后变成：

即：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead=new ListNode(0);
        dummyhead->next=head;
        ListNode* cur=dummyhead;
       //注意终止条件，同时cur->next！=NULL要放在cur->next->next!=NULL前面，因为不先判断cur->next是否为空，cur->next->next可能报错
        while(cur->next!=NULL&&cur->next->next!=NULL)   
        {
            ListNode* tmp=cur->next;
            ListNode* gmp=cur->next->next->next;
            cur->next=cur->next->next;
            cur->next->next=tmp;
             cur->next->next->next=gmp;
            cur=cur->next->next;
            
        }
        head=dummyhead->next;
        delete dummyhead;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：遍历链表中每个元素一次，所以时间复杂度为O(n)
空间复杂：使用了两个额外的变量存储中间值，空间复杂度为O(1)

本题收获

1.本题使用了虚拟头节点的方法，简化了对头节点的处理。
2.本题主要还是需要通过画图，拟清节点之间的指向关系，同时将节点的指向关系在图形上简化，便于代码的书写。刚开始写这道题的时候容易写不清楚三个步骤的指向关系。

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

题目链接：删除链表倒数第N个节点
本题采用双指针解法，思路是如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，然后删掉slow所指向的节点就可以了。
删除过程主要分为以下几步：
（1）采用虚拟头节点dummyhead，定义双指针fast指针和slow指针，分别初始化为虚拟头节点dummyhead;
（2）fast首先走n + 1步 ，fast指针移动n+1，是因为只有这样同时移动的时候slow指针才能指向删除节点的上一个节点（方便做删除操作）；
（3）fast和slow同时移动，直到fast指向末尾；
（4）删除slow指向的下一个节点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead=new ListNode(0);
        dummyhead->next=head;
        n++;
        ListNode* fast=dummyhead;
        ListNode* slow=dummyhead;
        while(n--&& fast!=NULL)
        {
            fast=fast->next;
        }
        while(fast!=NULL)
        {
            fast =fast->next;
            slow =slow->next;
        }
        slow->next=slow->next->next;
        head=dummyhead->next;
        delete dummyhead;
        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

本题收获

1.双指针的应用，刚拿到题目时考虑采用双指针，但没有想到通过先移动一个指针的方式找到倒数第N个节点，通过本题对快慢指针的应用可以灵活处理有了新的认识。
2.删除操作注意要使慢指针指向需要删除节点的前一个节点，这样便于完成删除操作。

面试题02.07. 链表相交

题目链接：链表相交
本题就是求两个链表交点节点的指针。 这里要注意，交点不是数值相等，而是指针相等。
两个单链表存在交点，则交点以及交点以后的节点应当相同，两个链表应该存在公共的尾部。

方法一：

为了方便举例，假设节点元素数值相等，则节点指针相等。
下图两个链表，curA指向链表A的头结点，curB指向链表B的头结点：

求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA=headA;
        ListNode* curB=headB;
        int lenA=0,lenB=0;
        int gap=0;
        while(curA!=NULL)
        {
        lenA++;
        curA=curA->next;
        }
        while(curB!=NULL)
        {
        lenB++;
        curB=curB->next;
        }
        curA=headA;
        curB=headB;
        // 让curA为最长链表的头，lenA为其长度
        if(lenB>lenA)
        {
        swap(curA,curB);
        swap(lenA,lenB);
        }
        //求长度差
        gap=lenA-lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while(gap--)
        {
            curA=curA->next;
        }
        while(curA!=NULL)
        {if(curA==curB) //注意这里是判断指针相等
        {
           return curA; 
        }
            curA=curA->next;
            curB=curB->next;
        }
        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
31
32
33
34
35
36
37
38
39
40
41
42
43

方法二：

设第一个公共节点为node，链表A的节点数为a，链表B的节点数为b，两链表的公共尾部节点数为c。则有：

• 头节点 headA 到 node 前，共有 a−c 个节点
• 头节点 headB 到 node 前，共有 b−c 个节点
  

设两个节点指针 curA​ , curB 分别指向两链表头节点 headA , headB ，做如下操作：
（1）指针curA 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a + (b - c)
（2）指针curB 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b + (a - c)
如下式所示，a + (b - c) = b + (a - c)，此时指针curA , curB 重合，并有两种情况：
若两链表有公共尾部 (即 c > 0 ) ：指针curA , curB 同时指向第一个公共节点node 。
若两链表无公共尾部 (即 c = 0) ：指针curA , curB 同时指向null。
因此返回curA 即可。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA, *curB = headB;
        while (curA != curB) {
            curA = curA != nullptr ? curA->next : headB;
            curB = curB != nullptr ? curB->next : headA;
        }
        return curA;
    }
};
1
2
3
4
5
6
7
8
9
10
11

本题收获

1.本题需要明确是判断指针相等，不是数值相等
2.两个单链表存在交点，则交点以及交点以后的节点应当相同，两个链表存在公共的尾部，因此通过将两个链表末尾对齐可以寻找相交的节点。

leetcode 142.环型链表2

题目链接：环型链表2
本题主要包含两个方面的问题：

• 判断链表是否有环
• 如果链表有环，如何找到环的入口

方法一：快慢指针

（1）判断链表是否有环

使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
原理：
第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇。
第二点：因为fast是走两步，slow是走一步，考虑相对速度，相对于slow来说，fast是1个节点1个节点的靠近slow的，不可能跳过slow，所以fast一定可以和slow重合。

（2）在有环条件下，寻找环的入口点

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

相遇时，slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数。由于fast指针一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数*2 ，
(x + y) * 2 = x + y + n (y + z)
即 x + y = n (y + z)
因为要找环形的入口，那么要求的是x，x表示头结点到 环形入口节点的的距离。
x = n (y + z) - y
再从n(y+z)中提出一个 （y+z）来，整理之后：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
考虑到n的含义，以n=1为例，fast指针在环形里转了一圈之后，就遇到了 slow指针。此时公式就化解为 x = z，这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
那么通过在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。让index1和index2同时移动，每次移动一个节点， 那么两个指针相遇的地方就是环形入口的节点。
如果 n>1，就是fast指针在环形转n圈之后才遇到 slow指针。这种情况和n=1的时候效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，index1指针在环里多转了(n-1)圈，然后再遇index2，相遇点依然是环形的入口节点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        ListNode* index1;
        ListNode* index2;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if(fast==slow)    
            {
              index1=fast;
              index2=head;   
              while(index1!=index2)
              {
                index1=index1->next;
                index2=index2->next;
              }
               return index1;
            }
        }
      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

时间复杂度：O(n)，判断快慢指针相遇时时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(n)+O(n)=O(n)。
空间复杂度：O(1)，只使用了fast，slow，index1,index2四个指针。

方法二：哈希表

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度O(n)
空间复杂度O(n)

本题收获

1.本体需要拆解为两个问题，一是先判断链表是否有环，二是在判断有环的基础上，再找环的入口点。
2.通过快慢指针的方法来判断链表是否有环，在判断环的入口点时需要理清链表移动位置之间的数学关系
3.可以通过哈希表对遍历的节点进行记录，从而找到第一个被重复记录的节点即为入口点