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

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

题目：. - 力扣（LeetCode）

思路：这题关键是要每次进行两个结点的操作，并且每次都要保存其前结点，做题思路比较清晰，但是总是处理不好边界问题，总是越界。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
    ListNode* virhead=new ListNode(0,head);
    ListNode* pre=virhead;
    ListNode* cur=head;
    while(cur!=NULL&&cur->next!=NULL){
        pre->next=cur->next;
        cur->next=cur->next->next;
        pre->next->next=cur;
        pre=cur;
        cur=cur->next;
    }
    return virhead->next;
    }
};

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

题目：. - 力扣（LeetCode）

思路：最开始想到的是最简单的两次遍历，之后看卡哥的文章学会了快慢双指针一次遍历完成。

代码：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next;
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        return dummyHead->next;
    }
};

面试题 02.07. 链表相交 

题目：. - 力扣（LeetCode）

思路：看提示做的，关键是通过遍历来得到长度差。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* temA=headA;
        ListNode* temB=headB;
        int a=1,b=1;
        if(headA==NULL||headB==NULL)
        return NULL;
        while(temA->next!=NULL)
        {
            temA=temA->next;
            a++;
        }
        
        while(temB->next!=NULL)
        {
            temB=temB->next;
            b++;
        }
        if(temA!=temB)
        return NULL;
        temA=headA;
        temB=headB;
        if(b>a){
            swap(a,b);
            swap(temA,temB);
        }
        int gap=a-b;
        for(int i=0;i<gap;i++){
            temA=temA->next;
        }
        while(temA!=temB){
            temA=temA->next;
            temB=temB->next;
        }
        return temA;
    }
};

142.环形链表II 

题目：. - 力扣（LeetCode）

思路：服力，这不是纯纯数学题吗？应该是追击问题吧，用快慢指针解决。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode*fast=head;
        ListNode*slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)
            {
             ListNode* index1=fast;
             ListNode* index2=head;
             while(index1!=index2)
             {
                index1=index1->next;
                index2=index2->next;
             }
             return index1;
            }
        }
        return NULL;
    }
};

总结：这次算法题整体不算太难，就是数学题不太会