Day4——两两交换链表节点、删除链表第n个绩点、链表相交、环形链表||_struct listnode* p1怎么指向head

今天是算法训练的第四天。

目录

前言

一、两两交换链表节点

解题思路

二：删除链表第n个绩点

1、解题思路

三、链表相交

1、解题思路

四、环形链表||

解题思路：

总结

---

前言

今日文案：

喷泉之因此美丽，是正因水有了压力。瀑布之因此壮观，是正因水有了落差。人的成长和进步也一样，人没有压力，潜能得不到开发，智慧就不能开花，最大的损失还是自我。偶尔给自我一点压力，适时让自我绽放一次，你会发现其实自我很优秀，很超凡。

---

一、两两交换链表节点

题目描述：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

题目来源：

力扣

解题思路

要操控两个相邻节点反转，就是把他们的连接改变，看图：

 那要改变指向，我们一定要注意保存好地址，不然一不小心就不见了。

代码如下：

struct ListNode* swapPairs(struct ListNode* head){
    
    struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummyhead->next=head;        //创建一个虚拟头节点，然后改变后面两个的位置，不用考虑头节点问题
 
    struct ListNode*cur=dummyhead;        //先站在头节点
    while(cur->next&&cur->next->next)        //一定要先判段cur->next，不然会出错
    {
        struct ListNode*temp1=cur->next;        //保存好位置，为下面跳转做准备
        struct ListNode*temp2=cur->next->next->next;
 
        cur->next=cur->next->next;
        cur->next->next=temp1;
        temp1->next=temp2;
        cur=cur->next->next;
    }
    return dummyhead->next;                //返回的头节点
}

画图多看几遍总能理解的，加油！建议去代码随想录看看，卡哥的动态图很好，我这做不出来，纯粹学习笔记，不好意思哈~

---

二：删除链表第n个绩点

题目描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

题目来源：

力扣

1、解题思路

快慢指针是重点！

假设我们要删除倒数第二个点，图解：

代码如下：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
 
    struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummyhead->next=head;
    
    struct ListNode* fast=dummyhead;
    struct ListNode* slow=dummyhead;        //虚拟头节点开始，不用判断头节点问题
    
    n=n+1;                                //因为从虚拟节点开始，走多一步才行
 
    while(n--&&fast)
    {
        fast=fast->next;                    //fast移动n步
    }
 
    while(fast)
    {
        slow=slow->next;                //当fast指向0，结束
        fast=fast->next;
    }
 
    slow->next=slow->next->next;        //删除（后面还应该手动释放内存呦，做题就不需要而已）
 
    return dummyhead->next;
}

---

三、链表相交

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

题目来源：

力扣

1、解题思路

我们最先要注意的一个点是，相交是指地址一样，而不是里面的值一样。

那一长一短的两个链表，我们要怎么算呢，先对齐！对齐之后我们再一步一步遍历去判定是否相等，因为长链表多出来那一部分肯定是在节点之前的，可以先放掉，判断后面的。

如图（来自代码随想录）：

 

 

代码如下：

struct ListNode *myfing(struct ListNode *p1,struct ListNode *p2)
{
    while(p1)                //比较地址
    {
        if(p1==p2)            //如果地址相等，那就返回
        return p1;        
        else
        {
            p1=p1->next;        //不相等继续走下去，直到为0，也就是不相交的情况
            p2=p2->next;
        }
    }
    return NULL;
}
 
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode * w=0;
    struct ListNode *p1=headA,*p2=headB;
    int length_a=0,length_b=0,s=0;
    while(p1)                        //找出两个链表的长度
    {
        length_a++;
        p1=p1->next;
    }
    while(p2)
    {
        length_b++;
        p2=p2->next;
    }
 
    p1=headA;
    p2=headB;
    if(length_a>length_b)        //然后移动到一起开始的地方
    {
        s=length_a-length_b;
        while(s--)
        {
            p1=p1->next;
        }
        w=myfing(p1,p2);
    }
    else
    {
        s=length_b-length_a;
        while(s--)
        {
            p2=p2->next;
        }
        w=myfing(p1,p2);
    }
    return w;
}

---

四、环形链表||

题目描述：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

题目来源：

力扣

解题思路：

这个题真的太精妙了，直接看题解，醍醐灌顶hhh。

这里直接上代码了：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *fast=head;        //快慢指针
    struct ListNode *slow=head;
 
    while(fast&&fast->next)
    {
        fast=fast->next->next;  //fast一次走两步，slow一次走一步，进入循环后等于每次一步接近
        slow=slow->next;
        if(fast==slow)            //快慢指针相遇时
        {
            struct ListNode *p2=fast;        //记录位置
            struct ListNode *p1=head;
            while(p1!=p2)                    //遍历到两个指针相遇
            {
                p1=p1->next;
                p2=p2->next;
            }
            return p1;                    //返回入口值
        }
    }
    return 0;                //无入口返回0.
 
}

加油，继续学习。

---

总结

写得不好，请多指教。希望每天进步一点点，冲冲冲。