链表OJ题-阿里云开发者社区

链表OJ题

2023-09-02 39

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 链表OJ题

今天讲一些关于链表的Oj题，相信你看完对链表又提升一个档次。

题目一

思路一

遍历一遍链表是Val值得时候free这个，然后我们往后走，一直走到末尾空指针得时候，新链表就是我们得答案，那我们用代码来表示一下吧。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur=head;
    struct ListNode*pre=NULL;
   while(cur)
   {
       if(cur->val==val)
       {
           if(pre==NULL)
           {
               head=cur->next;
               free(cur);
               cur=head;
           }
          else
          {
             pre->next=cur->next;
           free(cur);
           cur=pre->next;
          }
       }
       else
       {
           pre=cur;
           cur=cur->next;
       }
   }
   return head;
}

思路二

不是val我们就拿下来，是val就跳过，放到新链表中。

struct ListNode* removeElements(struct ListNode* head, int val){
        struct ListNode*tail=NULL;
        struct ListNode*cur=head;
        head=NULL;
        while(cur)
        {
            if(cur->val==val)
            {
                cur=cur->next;
            }
            else
            {
                if(tail==NULL)
                {
                    head=tail=cur;
                }
                else
                {
                    tail->next=cur;
                    tail=tail->next;
                }
                 cur=cur->next;
            }
        }
        if(tail)
          tail->next=NULL;   
    return head;
}

思路三

带哨兵位得头节点得方法，是val拿下来，不是跳过。

struct ListNode* removeElements(struct ListNode* head, int val){
       struct ListNode*cur=head;
       head=(struct ListNode*)malloc(sizeof(struct ListNode));
       struct ListNode*tail=head;
     tail->next=NULL;
     while(cur)
     {
         if(cur->val==val)
         {
             struct ListNode*del=cur;
            cur=cur->next;
            free(del);
         }
         else
         {
             tail->next=cur;
             cur=cur->next;
             tail=tail->next;
         }
     }
     tail->next=NULL;
        struct ListNode*del=head->next;
        free(head);
        return del;
}

题目二

这题我们可以改变指向，给三个指针变量，变方向就可以解决。

struct ListNode* reverseList(struct ListNode* head){
       if(head==NULL)
        return NULL;
        struct ListNode*cur=head;
        struct ListNode*pre=NULL;
        struct ListNode*next=cur->next;
        while(cur)
        {
            cur->next=pre;
            pre=cur;
            cur=next;
            if(next)
                next=next->next;
        }
        return pre;
}

思路二

头插到新链表就可以了。

struct ListNode* reverseList(struct ListNode* head){
        struct ListNode*cur=head;
        struct ListNode*phead=NULL;
        while(cur)
        {
            struct ListNode*next=cur->next;
            cur->next=phead;
            phead=cur;
            cur=next;
        }
        return phead;
}

题目三

用快慢指针，快走两步，慢走一步，就可以解决。

struct ListNode* middleNode(struct ListNode* head){
        struct ListNode*slow=head;
        struct ListNode*fast=head;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next;
            if(fast)
            fast=fast->next;
        }
        return slow;
}

题目四

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*slow=pListHead;
     struct ListNode*fast=pListHead;
     while((k--))
     {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
     }
     while(fast)
     {
        fast=fast->next;
        slow=slow->next;
     }
     return slow;
}