• 【数据结构】链表OJ题（建议收藏！！！）

    注意OJ题，传过来的一般是指向头结点的头指针，而非带哨兵卫的头结点。

    文章目录

    一.移除链表元素

    在这里插入图片描述

    解题思路1：不建立哨兵卫

    （1）着重利用到两个指针，cur（即当前位置，去寻找值为val的重要指针），prev（指向cur前面的一个结点），利用这两个指针移除链表中的特定元素。
    （2）刚开始cur指向头结点，而prev被初始化为NULL（不然就会沦为野指针），cur会在每次循环后，遍历移向下一个结点，所以当cur为NULL时，跳出循环，如果cur指向的结点值不为val，则cur跳过此结点，指向下一个结点，在这步指向之前，要把cur的位置先赋给prev。
    （3）当cur指向的结点值为val，则要删除当前结点。在这里分为两种情况，要删除的是头结点，和不是头结点。如果是头结点，第一步替换头结点，head=head->next;第二步：释放头结点，free（cur），第三步：重置cur，cur=head。如果不是头结点，第一步断开连接，让prev->next=cur->next,第二步释放次结点，free(cur),第三步cur指向此节点的下一个结点，即cur=prev->next;
    >图解：
    在这里插入图片描述

    代码实现：

    struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur=head,*prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
           //1.头删
           if(cur==head)
           {
                head=head->next;
                free(cur);
                cur=head;
           }
           //2.非头删
           else
           {
               prev->next=cur->next;
               free(cur);
               cur=prev->next;
           }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    解题思路2：建立新链表

    解题思路：
    在这里插入图片描述

    struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur=head;
    struct ListNode* newhead=NULL,*tail=NULL;

    while(cur)
    {
        if(cur->val!=val)
        {
            if(tail==NULL)
            {
                newhead=tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
            cur=cur->next;
        }
        else
        {
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
    }
    //最后一个结点为val时，注意将最后一个结点的指针域指向空
    if(tail)
    {
        tail->next=NULL;
    }
    return newhead;
}

    • 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

    解题思路3：建立哨兵卫

    带哨兵卫后（头结点，但只有指针域），代码变得更加简洁，建立新链表时，不需要判断tail是否为NULL，让tail=guard后，即可连接符合条件的结点。一定要记住，若最后一个结点为val，要记住把tail->next==NULL。
    *注意我们建立的新节点最后也需要释放。并且最开始要把guard->next置为空，不然它将会是一个野指针，当传过来的是空链表，那么程序就会报错。
    在这里插入图片描述

    struct ListNode* removeElements(struct ListNode* head, int val)
{
   struct ListNode* cur=head;//cur勇于遍历原链表
   struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
   guard->next=NULL;//若原链表为NULL
   struct ListNode* tail=guard;//tail指向头结点

   while(cur)
   {
       if(cur->val!=val)
       {
           tail->next=cur;//连接符合条件的结点
           tail=tail->next;//更新tail
           cur=cur->next;//更新cur
       }
       else
       {
           struct ListNode* del=cur;//保存val的位置
           cur=cur->next;
           free(del);
       }
   }
   //最后结点为val
   if(tail)
   {
       tail->next=NULL;
   }
   head=guard->next;
   free(guard);
   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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    二.合并两个有序链表

    在这里插入图片描述

    解题思路：创建新的链表
    （1）两个指针分别遍历两个链表
    （2）建立哨兵卫，tail尾指针，cur->val较小值进行连接，注意指针指向的更新。
    （3）注意有一个有序链表会先连接完成，那么会退出循环，注意我们还需要将剩下一个链表的其余结点连接上去
    （4）注意释放哨兵卫的头结点
    （5）若传过来的是空链表，那么刚开始我们要把guard->next置为空，不然它将沦为野指针。
    （6）这里因为原链表最后已置为空，不像上道题目一样，可能会把最后一个结点删除，所以我们不用考虑这层。
    在这里插入图片描述
    代码实现

    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* guard=(struct ListNode* )malloc(sizeof(struct ListNode));
    guard->next=NULL;

    struct ListNode* cur1=list1,* cur2=list2;
    struct ListNode* tail=guard;


    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next=cur1;
            cur1=cur1->next;
        }
        else
        {
            tail->next=cur2;
            cur2=cur2->next;
        }
        tail=tail->next;
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    struct ListNode* head=guard->next;
    free(guard);
    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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    三.翻转链表

    在这里插入图片描述

    解题思路1：头插

    （1）定义一个新的指针newnode,进行头插，注意更新头指针。
    （2）两个指针cur，next，用于前后遍历原链表，next指针用于保存cur下一个结点的位置，cur是要进行头插的结点。注意每次循环都要更新这两个指针的位置。
    在这里插入图片描述

    struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newnode = NULL;

    while(cur)
    {
        struct ListNode* next=cur->next;//保留cur下一个结点的地址
        cur->next=newnode;
        newnode=cur;

        cur=next;
    }
    return newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    解题思路2：翻转

    （1）需要3个辅助指针，当n2指向NULL时跳出循环；
    （2）三个指针进行迭代
    （3）注意传过来的若为空指针，n3不能直接置成，n3=n2->next,这是错误的示范。所以要先判断n2是否为NULL。
    在这里插入图片描述

    struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* n1,*n2,*n3;
   n1=NULL;
   n2=head;
   n3=NULL;

   while(n2)
   {
       n3=n2->next;
       n2->next=n1;
       
       //迭代
       n1=n2;
       n2=n3;
   }
   return n1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    四.链表的中间结点

    在这里插入图片描述

    解题思路1：遍历
    因为这道题目没有时间复杂度的要求，所以要解决这道题，我们只需要先遍历一遍链表，统计链表的结点个数，然后再遍历一遍链表，寻找中间结点即可。此方法的时间复杂度为o(n^2)。

    struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* cur=head;
    int count=0;

    while(cur)//遍历链表
    {
        count++;
        cur=cur->next;
    }
    int mid=count/2;
    struct ListNode* midnode=head;
    while(mid--)
    {
        midnode=midnode->next;
    }
    return midnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    解题思路2：快慢指针

    我们也可以只遍历一遍链表，就找到中间结点，这样时间复杂度就为O(n).
    利用的方法是快慢指针。那么什么是快慢指针呢？
    快指针一次走两步，慢指针一次走一步，那么当快指针走到空时，慢指针走到一半，之后返回慢指针指向的地址即可。
    在这里插入图片描述在这里插入图片描述

    struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast,*slow;
    fast=slow=head;

    while(fast&&fast->next)
    {
        slow=slow->next;//慢指针走一步
        fast=fast->next->next;//快指针走两步
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    五.链表中倒数第k个结点

    在这里插入图片描述

    要求只遍历一遍，即时间复杂度为O(n).
    方法：利用快慢指针
    fast先走k步
    在这里插入图片描述

    struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* fast,*slow;
    fast=slow=pListHead;
    //while(--k)// k-1步
    while(k--)//k步
    {
        //1.传过来的是空链表
        //2.k>=结点数
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    六.链表分割

    测试用例：
    在这里插入图片描述

    （1）普通情况
    在这里插入图片描述

    （2）当最后一个小于x时，会造成环状，最后返回的是val4这个结点，所以val7的结点一定要置为空
    在这里插入图片描述

    （3）当传过来的为空指针，我们的输出也为{}空，所以防止 lessTail->next=greaterGuard->next;出错，我们一开始得把新建的两个哨兵卫结点的next置NULL

    class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* lessGuard,*lessTail,*greaterGuard,*greaterTail;
        lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterGuard=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        //注意置空
        lessGuard->next=NULL;
        greaterGuard->next=NULL;
        
        //cur遍历原链表
        struct ListNode* cur=pHead;
        
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;//连接符合条件的cur
                lessTail=lessTail->next;//更新指针
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            cur=cur->next;
      }
      //连接俩链表
        lessTail->next=greaterGuard->next;
        greaterTail->next=NULL;
        
        pHead=lessGuard->next;
        free(greaterGuard);
        free(lessGuard);
        
        return pHead;
     }
};

    • 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

    七.链表的回文结构

    测试用例：
    在这里插入图片描述

    class PalindromeList {
public:
   
    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* slow,*fast;
        slow=fast=head;
        
        while(fast&&fast->next)
        {
            slow=slow->next;//走一步
            fast=fast->next->next;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* n1,*n2,*n3;
        n1=NULL;
        n2=head;
        n3=NULL;
        while(n2)
        {
            n3=n2->next;
            n2->next=n1;
            
            //迭代
            n1=n2;
            n2=n3;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* head)
    {
        //1.找中间结点
        struct ListNode* mid=middleNode(head);
        //2.逆序包括中间结点在内之后的结点
        struct ListNode* rmid=reverseList(mid);
        
        while(head&&rmid)
        {
            //判断回文
            if(head->val!=rmid->val)
            {
                return false;
            }
            head=head->next;
            rmid=rmid->next;
        }
        return true;
    }
};

    • 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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    八.相交链表

    在这里插入图片描述

    1.思路：想找到俩链表相交的结点，即需要俩链表的最后一个结点的next指针域指向的结点地址相同；（注意而非val相同）
    2.要求：时间复杂度为O(n+m),空间复杂度为O(1);
    3.方法：（1）是否相交->俩链表的尾结点是否相等；
    （2）求出俩链表的长度lenA，lenB
    （3）较长的链表先走 差距步 ，然后再俩链表同时走，第一个结点地址相等，那就是链表交点。
    （4）注意空链表无结点

    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1;
    int lenB=1;
    //计算链表长度，找到尾结点
    while(curA)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB)
    {
        curB=curB->next;
        lenB++;
    }
    //如果俩链表遍历到最后的结点地址不相同
    //则两链表不相交
    if(curA!=curB)
    {
        return NULL;
    }
    struct ListNode* shorttail=headA;
    struct ListNode*longtail=headB;
    if(lenA>lenB)
    {
        shorttail=headB;
        longtail=headA;
    }
    //先走差距步
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longtail=longtail->next;
    }
    
    while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
    {
        if(longtail==shorttail)//相等时返回结点
        {
            return shorttail;
        }
        else
        {
            longtail=longtail->next;
            shorttail=shorttail->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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    九.环形链表I

    注意环形链表不能遍历
    在这里插入图片描述

    测试用例：
    在这里插入图片描述

    解题思路1：

    方法：快慢指针
    fast指针一次走两步，slow指针一次走一步
    在这里插入图片描述
    在这里插入图片描述

    代码实现：

    bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast,*slow;
    //1.快慢指针指向头结点
    fast=slow=head;
    //2.追赶
    //因为fast走的比slow快
    //若有环则循环
    //若无环fast会先指向NULL，跳出循环
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        //慢指针一次走一步
        //快指针一次走两步
        //走一次，差距缩小一步
        //直到相遇
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    思考问题1:

    （1）请问，slow一次走一步，fast一次走三步，是否可以？
    假设slow进环后，fast和slow之间差距N，那么追赶的距离就是N；
    这种情况下，每追赶一次，他们之间的距离就缩小2步。·如果追赶的距离N是偶数，就追得上；
    若N是奇数，意味着fast与slow，在第一次中，不会刚好相遇，会出现以下这种情况，于是他们之间的距离就变成了C-1(C是环的长度)，并进入新一轮的追赶，在这种情况下，若C-1是偶数，则这一轮追得上，若C-1是奇数，则永远追不上。
    在这里插入图片描述
    （2）请问，slow一次走一步，fast一次走X步，是否可以？
    （3）请问，slow一次走Y步，fast一次走X步（X>Y）,是否可以？
    与上面的情况同理，能否追赶上取决于，每追赶一次，slow和fast指针的距离是缩小偶数倍，还是奇数倍，并且取决于环的长度。

    十.环形链表II

    在这里插入图片描述
    这道题与上道题大近相同，这道题要判断链表是否有环，还需要返回链表开始入环的第一个结点（即L的位置）,如果链表无环，则返回NULL。

    解题思路1：公式推导

    由上述环状链表可得，fast快指针一次走两步，slow一次走一步，所以得出公式：fast走的距离=2*slow走的距离。
    （1）假设进环前的长度是L，环的长度是C，入口点到相遇点距离是X
    （2）则slow走的距离是：L+X；fast走的距离是：L+N*C+X;（假设slow进环，fast在环里面已经转了N圈，N>=1）
    （3）推导公式：
    2(L+X)=L+NC+X
    L+X=NC
    L=NC-X
    L=(N-1)C+C-X
    可以这么说：一个指针A从头开始走，一个指针B从相遇点开始走，他们会在入口点相遇
    在这里插入图片描述

    struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow, *fast;
    slow=fast=head;

    while(fast&&fast->next)//若为空，则无环
    {
        slow=slow->next;
        fast=fast->next->next;
        //直到相遇
        if(slow==fast)
        {
            struct ListNode* meet=slow;
            //一个指针从头开始走，一个指针从相遇点开始走
            //他们会在入口点相遇
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return head;//or meet
        }
    }
    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

    解题思路2：转换成相交问题

    1.找到交点(slow==fast);
    2.保留链表交点下一个结点的地址
    3.断开链表
    4.找链表交点
    5.恢复链表

    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1;
    int lenB=1;
    //计算链表长度，找到尾结点
    while(curA)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB)
    {
        curB=curB->next;
        lenB++;
    }
    //如果俩链表遍历到最后的结点地址不相同
    //则两链表不相交
    if(curA!=curB)
    {
        return NULL;
    }
    struct ListNode* shorttail=headA;
    struct ListNode*longtail=headB;
    if(lenA>lenB)
    {
        shorttail=headB;
        longtail=headA;
    }
    //先走差距步
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longtail=longtail->next;
    }
    
    while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
    {
        if(longtail==shorttail)//相等时返回结点
        {
            return shorttail;
        }
        else
        {
            longtail=longtail->next;
            shorttail=shorttail->next;
        }
    }
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast, *slow;
    fast=slow=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        {
            //相遇点
            struct ListNode* meet=slow;
            //保存相遇点的下一个结点
            struct ListNode* next=meet->next;
            //断开环
            meet->next=NULL;

            //恢复环
            struct ListNode* entryNode=getIntersectionNode(next,head);//找交点
            meet->next=next;
            return entryNode;

        }
    }
    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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
  • 相关阅读:
    Linux发展历程
    MogaFX—尼日利亚未能实现其金融包容性目标
    redis我记不住的那些命令（一）
    四川云汇优想教育咨询有限公司电商服务正规吗
    Kubernetes 笔记 / 生产环境
    学习笔记-java代码审计-文件操作
    SQL中的LAG函数与LEAD函数用法
    docker更新正在运行中的容器内存
    day59
    QT作业三
  • 原文地址：https://blog.csdn.net/weixin_63449996/article/details/126154554