代码随想录算法训练营第四天|链表part02

方法一：交换值

/**
 * 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*curNode=head;
        while( curNode&&curNode->next){//这里不能仅判断curNode->next 因为curNode是空
            ListNode* nextNode=curNode->next;
            int curV=curNode->val;
            curNode->val=nextNode->val;
            nextNode->val=curV;
            curNode=nextNode->next;
        }
        return head;
    }
};

错误代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode*dummyNode=new ListNode;
        dummyNode->next=head;
        ListNode*curNode=dummyNode;
        
        while( curNode->next&&curNode->next->next){
        auto temp=curNode->next;
        auto temp1=curNode->next->next->next;
        temp->next=temp1;//这里提前绑定 会出现回路导致超时
        curNode->next=curNode->next->next;
        curNode->next->next=temp;
        // curNode->next->next->next=temp1;
        curNode=curNode->next->next;
        }
        auto ans=dummyNode->next;
        delete dummyNode;
        return ans;
    }
};

正确解答：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //虚拟头节点
        ListNode*dummyNode=new ListNode;
        dummyNode->next=head;
        ListNode*curNode=dummyNode;
        
        while( curNode->next&&curNode->next->next){
        //交换
        auto temp=curNode->next;
        auto temp1=curNode->next->next->next;
        curNode->next=curNode->next->next;
        curNode->next->next=temp;
        curNode->next->next->next=temp1;
        curNode=curNode->next->next;
        }
        auto ans=dummyNode->next;//这里是必须的 因为头指针会被换到后一个去了
        delete dummyNode;
        return head;
    }
};

思路：

遍历一遍链表 统计有多少个节点 然后再计算出被删除节点前一个节点的编号

遍历到被删除节点前一个节点  然后再进行删除操作

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode*dummyHead=new ListNode(0);
        dummyHead->next=head;
        auto cur=dummyHead;
        int length=0;
        while(cur){
            length++;
            cur=cur->next;
        }
        auto pre=dummyHead;
        int count=length-n-1;
        while(count--){
            pre=pre->next;
        }

        if(pre&&pre->next){
            pre->next=pre->next->next;
        }
        auto ans=dummyHead->next;
        delete dummyHead;
        return ans;
    }
};

事实上 有更好的方法 这题是典型的应用快慢指针的方法

快指针先走n步

然后快慢指针一起走

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

    }
};

思路：

也是用快慢指针

先分别求两个链表的长度

然后比较长度 长的先走

然后再一起走 判断当前指针是否相同

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lengthA=0;
        auto curA=headA;
        while(curA){
            lengthA++;
            curA=curA->next;
        }
        int lengthB=0;
        auto curB=headB;
        while(curB){
            lengthB++;
            curB=curB->next;
        }

        if(lengthA>=lengthB){
            int dis=lengthA-lengthB;
            while(dis--){
                headA=headA->next;
            }
            while(headA){
                if(headA==headB)return headA;
                headA=headA->next;
                headB=headB->next;
                
            }
        }else{
            int dis=lengthB-lengthA;
            while(dis--){
                headB=headB->next;
            }
            while(headA){
                if(headA==headB)return headA;
                headA=headA->next;
                headB=headB->next;
            }

        }
        return NULL;
        
    }
};

思路：

同样是用快慢指针

快指针每次走两格，慢指针每次走一格。

有环一定会相遇

无环则不会相遇

假设相遇的地方在E

从头到环入口的距离为x

从入口到相遇的距离为y

从相遇到入口的距离为z

可以推出：

x=(n-1)(y+z)+z

说明此时 在相遇的地方定义一个指针index1

头定义一个指针index2

两者一起走 他们相遇的地方就是环的入口

/**
 * 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) {
        auto fast=head;
        auto slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){//相遇
                auto index1=slow;
                auto index2=head;
                while(index1!=index2){ //一起移动
                    index1=index1->next;
                    index2=index2->next;
                }
                return index1;
            }
        }
        return NULL;
        
    }
};