数据结构-单链表-力扣题

目录

移除链表元素

反转链表

链表的中间节点

返回倒数第k个节点 

合并两个有序列表 

分割链表

链表的回文结构

 相交链表:找两个链表的公共节点

环形链表:判断链表中是否有环

 环形链表 II:要求返回入环的第一个节点


移除链表元素

题目链接:力扣(LeetCode)

思路:和前面学的单链表的中间删除数据一样,使要被删除节点的前一个节点指向下要被删除节点的下一个节点,然后把要被删除的节点free掉。

 具体实现过程:先定义prev和cur,让cur指向头节点,遍历链表,如果cur->val!=val,让prev指向cur,cur指向cur的下一个节点,(prev始终在cur前面一个节点),当cur->val=val时停下,让prev的下一个节点指向cur的下一个节点,删除它们中间的cur节点,然后让cur重新指向prve->next,这就实现了节点的删除。但是还有一种情况如下图:

头节点的数据等于val,这时就需要判断了,如果头节点数据等于val,就要删除头节点,然后把head重新指向原来的头结点的下一个节点,cur重新指向head:

代码如下:

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

这道题还有一道解法,就是重新开辟一个节点,找到不相等的节点,尾插到该节点的后面

直接上代码:

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

反转链表

题目链接:力扣(LeetCode) 

思路:逆转链表中所有的箭头指向,如下图所示:

 首先,定义n1为null,定义n2为原链表的头节点,只要使n2下一个指向的是n1,然后把n2给你,n3给n2,这样进行迭代,直到链表的所有箭头全部反转,就实现了反转链表,注意:在每次循环开始的时候都要用n3保存n2的下一个节点位置,否则,n2改变指向后就找不到后面的节点了。

代码如下:(代码中用rhead替代n1,用cur替代n2,用next替代n3

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

链表的中间节点

题目链接:力扣(LeetCode)

思路:定义快慢指针fast和slow,fast每次走两步,slow每次走一步,如果有奇数个节点,当fast走到最后一个节点时,slow就走到中间节点了,如果有偶数个节点,当fast走到空,slow就走到中间节点了。

 因此我们在循环时要判断,当fast和fast->next为空时就不能再继续了

代码如下:

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

返回倒数第k个节点 

 题目链接:力扣(LeetCode)

思路一: 上文我们讲了如何反转链表,这道题可以复用反转链表,先把链表整体反转,然后从前往后找第k个节点。

代码如下:

int kthToLast(struct ListNode* head, int k){
    struct ListNode*cur=head;
    struct ListNode*rhead=NULL;
   while(cur)
   {
       struct ListNode*next=cur->next;
       cur->next=rhead;
       rhead=cur;
       cur=next;
   }
   while(--k)
   {
       rhead=rhead->next;
   }
   return rhead->val;
}

思路二: 定义快慢指针fast和slow,先让fast走k步(或者k-1步),然后slow和fast一起走,直到fast为空就停止(如果先让fast走k-1步,则当fast->next为空时停止),这时slow节点就是要找的倒数第k个节点。 

fast先走k步: 

int kthToLast(struct ListNode* head, int k){
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow->val;
}

fast先走k-1步: 

int kthToLast(struct ListNode* head, int k){
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    int n=k-1;
    while(n--)
    {
        fast=fast->next;
    }
    while(fast->next)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow->val;
}

合并两个有序列表 

题目链接:力扣(LeetCode) 

思路: 创建一个新链表,比较链表list1和list2中的值,每次把较小的尾插在新节点的后面(如果相等,随便取其中一个尾插),直到链表list1和list2中有一个被遍历完,就停止循环。此时,如果list1先结束,list2中有剩余的节点,直接把剩下的节点尾插到新链表后面;同理,如果list2先结束,list1中有剩余,就把list1中剩余的节点位插到新链表后面。注意:如果list1开始就为空,直接返回list2;如果list2开始就为空,直接返回list1。

代码如下: 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode*newhead=NULL;
    struct ListNode*tail=newhead;

    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;

    while(list1&&list2)
    {
        if((list1->val)<=(list2->val))
        {
           if(tail==NULL)
            {
                tail=newhead=list1;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                tail=newhead=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    }
    
    if(list1)
        tail->next=list1;
    if(list2)
        tail->next=list2;
    return newhead;
}

上述代码看起来很复杂,因为在刚开始的时候,不管是list1大,还是list2大,我们都要判断新链表的头结点是不是为NULL,那如何能简化这个问题呢?

这里我们来介绍一下哨兵位的头结点哨兵位的头结点不存储有效数据,哨兵位的头结点相当于我们新开辟的一个节点,可以直接在其后面尾插而不用担心它是不是NULL,下图就是头结点和带哨兵位的头结点之间的区别:

下面我们用哨兵位来实现一下上题:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*tail=newhead;

    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;

    while(list1&&list2)
    {
        if((list1->val)<=(list2->val))
        {
                tail->next=list1;
                tail=tail->next;
                list1=list1->next;
        }
        else
        {
                tail->next=list2;
                tail=tail->next;
                list2=list2->next;
        }
    }
    
    struct ListNode*del=newhead;
    newhead=newhead->next;
    free(del);
    
    if(list1)
        tail->next=list1;
    if(list2)
        tail->next=list2;
    return newhead;
}

这就是哨兵位的优势了,当我们用malloc开辟一个新节点newhead,就可以直接在它后面尾插,最后把newhead指向它的下一个节点,然后释放newhead就行。哨兵位的使用让我们省略了很多判断过程。 

分割链表

题目链接:力扣(LeetCode)

思路:我们可以使用哨兵位的头节点,分别开辟一个“大链表”和“小链表”的头结点,把原链表中的比x小的尾插到小链表的头结点之后,把比x大的尾插到大链表的头结点之后,遍历完原链表,把大链表整体尾插到小链表后面,具体如下图:

 注意:最后要将哨兵位头结点释放掉。

这道题比较复杂,分很多种情况:

1.链表为空   

2.链表元素全大于x   

3.链表元素全小于x   

4.有大有小

代码如下:

struct ListNode* partition(struct ListNode* head, int x){
    //链表为空
    if(head==NULL) return NULL;
    //链表全小于x
    int l = 0;
    struct ListNode* tmp = head;
    while(tmp)
    {
        if(tmp->val>=x)
        {
            l = 1;
        }
        tmp = tmp->next;
    }
    if(l == 0)
    {
        return head;
    }
    tmp = head;
    //链表全大于x
    int g = 0;
    while(tmp)
    {
        if(tmp->val<=x)
        {
            g = 1;
        }
        tmp = tmp->next;
    }
    if(g == 0)
    {
        return head;
    }
    struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
    lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
    greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            lesstail->next=cur;
            lesstail=lesstail->next;
        }
        else
        {
            greatertail->next=cur;
            greatertail=greatertail->next;
        }
        cur=cur->next;
    }

    lesstail->next=greaterhead->next;
    greatertail->next=NULL;
    head=lesshead->next;
    free(lesshead);
    free(greaterhead);
    return head;
}

链表的回文结构

题目链接:链表的回文结构_牛客题霸_牛客网

 思路:这道题可以根据上面的题目代码来实现,先找到中间节点,然后把中间节点往后的链表反转,使用双指针,指针1从头节点开始,指针2从中间节点开始,比较它们的值,如果相等,分别往后移一位,直到指针2指向空,说明就是回文结构;如果不相等,说明不是回文结构。

代码如下:

class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

struct ListNode* reverseList(struct ListNode* head) {
   struct ListNode*cur=head;
   struct ListNode*rhead=NULL;
   while(cur)
   {
       struct ListNode*next=cur->next;
       cur->next=rhead;
       rhead=cur;
       cur=next;
   }
   return rhead;
}
    bool chkPalindrome(ListNode* phead) {
        struct ListNode*mid=middleNode(phead);
        struct ListNode*rmid=reverseList(mid);
        while(rmid)
        {
            if(phead->val==rmid->val)
            {
                 phead=phead->next;
                rmid=rmid->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

 相交链表:找两个链表的公共节点

题目链接:力扣(LeetCode)

思路: 首先先判断它们是不是相交链表,只要判断它们的尾节点是不是相同的就行,只要尾节点相同就必定相交,因为相交链表只能是"Y"型的,不可能是"X"型的,下面就要返回相交链表的公共节点了,可以计算一下两个链表的长度,让长链表先走长度差步,然后两个链表一起走,如果有相同节点,该节点就是公共节点,如果没有,说明两个链表没有公共节点。

代码如下:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*tailA=headA;
    struct ListNode*tailB=headB;
    int lenA=0;
    int lenB=0;
    while(tailA->next)
    {
        tailA=tailA->next;
        lenA++;
    }
    while(tailB->next)
    {
        tailB=tailB->next;
        lenB++;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode*longlist=headA;
    struct ListNode*shortlist=headB;
    if(lenA<lenB)
    {
       longlist=headB;
       shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
        return longlist;
}

环形链表:判断链表中是否有环

题目链接:力扣(LeetCode)

思路:使用快慢指针,快指针一次走两步,慢指针一次走一步,如果有环,快指针先进环,慢指针后进环,快指针一定会某一时刻追上慢指针,此时它们相等。如果没环,快指针一定会最终指向空。

代码如下:

bool hasCycle(struct ListNode *head) {
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        return true;
    }
    return false;
}

 环形链表 II:要求返回入环的第一个节点

题目链接:力扣(LeetCode) 

思路:双指针法,一个指针从头节点处开始走,一个指针从相遇处的节点开始走,当它们相等时就是入环节点。

推导过程:

代码如下:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            struct ListNode*meet=fast;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}