【C++】顺序表 链表 栈练习题第三弹来啦（每日小细节008）

我们前几天已经学过了线性表：顺序表，链表和栈，但是只有理论知识是绝对不够的，我给大家找了一些很经典的题目，一定要做到立马有思路哦

（如果还有小可爱没有看过我的顺序表，链表和栈的知识点说明，请看↓

顺序表

入门级别单链表

带头双向循环链表（进阶版本）

栈

）

另外前两篇练习文章在下面，一定要把前一篇文章好好弄懂再看着一篇哦

顺序表，链表和栈的练习

练习题第二弹

今天主要给大家分享链表的收尾习题 

1.1合并两个有序链表

 

其实很麻烦的这个题目，正常做的话因为是两个链表所以保存起来很复杂

但是我们可以用哨兵位解决这个问题

把每次比较的更小的节点拿下来放到哨兵位的后面

 

在更改好指向之后tail别忘了后移一个指向节点1

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode*guard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*tail=guard;
tail->next=NULL;
while(list1 && list2)
{
    if(list1->val < list2->val )
    {
        tail->next=list1;
        list1=list1->next;
        tail=tail->next;
    }
    else
    {
      tail->next=list2;
        list2=list2->next;
        tail=tail->next;
    }
}
while(list1)
{
     tail->next=list1;
        list1=list1->next;
        tail=tail->next;
}
while(list2)
{
     tail->next=list2;
        list2=list2->next;
        tail=tail->next;
}
return guard->next;
}

 

---

 1.2链表分割

其实写完这个题感觉和上一个简直一模一样啊，只不过这次的题目链表只有一个，但是要创建两个新的哨兵位，一个保存比所给值x更小的节点，更一个保存>=的 

最后返回更小链表哨兵位的下一个节点就可以了

struct ListNode*guard1=(struct ListNode*)malloc(sizeof(struct ListNode)); //保存比x更小的
       struct ListNode*guard2=(struct ListNode*)malloc(sizeof(struct ListNode));  //保存比x更大
struct ListNode*tail1=guard1;
struct ListNode*tail2=guard2;
tail1->next=NULL;
tail2->next=NULL;
        while(pHead)
        {
            if(pHead->val //需要把节点放在guard1之后
            {
                tail1->next=pHead;
                pHead=pHead->next;
                tail1=tail1->next;
            }
            else
            {
                tail2->next=pHead;
                pHead=pHead->next;
                tail2=tail2->next;
            }
        }
        //把guard1的尾巴接到guard2上
        tail2->next=NULL;
        tail1->next=guard2->next;
        pHead=guard1->next;
        free(guard1);
        free(guard2);
        guard1=NULL;
        guard2=NULL;
        return pHead;
    }

 

---

1.3链表的回文结构

 

 这哥对称结构很容易让人想到找到头指针，尾指针，都向中间走，但是你清醒一点，这是链表不是数组！！！！

可以找到中间节点之后（这个在前面找中间节点的题写过了找中间节点）

找到之后反转一下吧

比如123321 中间节点就是第二个3

反转之后就是123    123

如果不是回文结构12344569中间节点4

反转之后1234  4569显然不一样

所以代码 

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //找到中间节点
        struct ListNode *slow=A,*fast=A;
        while(fast&&fast->next)
        {
           fast=fast->next->next;
           slow=slow->next;
        }
        struct ListNode *cur=slow;
        struct ListNode *rhead=NULL;
        while(cur)
        {
                struct ListNode *next= cur->next;
                cur->next=rhead;
                rhead=cur;
              cur=next;
        }
        while(rhead)
        {
            if(rhead->val != A->val)
            {
                return false;
            }
            rhead=rhead->next;
            A=A->next;
        }
        return true;
    }
};

---

1.4判断两个链表是不是相交 

 

这个题真的是坑啊

首先我们来说一下常规思路

肯定是先看一看相不相交，然后如果相交，让两个链表啊从同一个起始位置开始，往后遍历到有相同的节点！！！是相同的节点而不是节点的val相等！！！！！！！！ 

但是我们可以假设就是相交的啊，做到最后如果没有相等的节点就直接返回NULL就可以啊~~~

其实思路不难直接上代码吧

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *cur1=headA;
    struct ListNode *cur2=headB;
    int countA=0,countB=0;
    while(cur1)
    {
         ++countA;
         cur1=cur1->next;
    }
    while(cur2)
    {
         ++countB;
         cur2=cur2->next;
    }
    //此时的count就记录了两个链表的长度
    cur1=headA;
    cur2=headB;
    int gap=abs(countA-countB);
    if(countA//B链更长，应该B先走差距步，让俩个链表起始位置一样
    {
        while(gap--)
    {
           cur2=cur2->next;
    }
    }
    else
    {
        while(gap--)
    {
           cur1=cur1->next;
    }
    }
    //走到这两个链表就是一样长
    //假设两个链表相交那么走会在末尾之前找到一个节点，两个val一样
    while(cur1)
    {
        if(cur1 == cur2)
        {
            return cur2;
        }
        else{
            cur1=cur1->next;
            cur2=cur2->next;
        }
    }
    return NULL;
}

 

---

1.5判断是否有环 

 

 其实这个题难的根本就不是代码，只要还是之快慢指针的逻辑，快指针走两步，慢指针走一步，如果有环，那么快慢指针最终会相遇~~~否则永远不会相遇

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

其实难的在于为什么快指针一定走两步，慢指针一定走一步才刚好合适？

---

1.6返回入环点 

 

 有了刚才的铺垫这个简直太简单了

区别就是在相遇之后记录一下相遇的位置，然后从相遇点和头分别往后走，第一次相遇的地方就是入环点

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

---

1.7带随机指针的深度拷贝

 

现在有了前面题目的铺垫这个也不算很难很难但是这个需要积累，方法就是把复制出来的节点像是跟班一样挂在原链表每一个节点后面，变成下面这样

每次创建一个新节点然后改变一下指向

最后再把复制的节点从原来的链表上拿下来

struct Node* copyRandomList(struct Node* head) {
    struct Node*tmp=head;
    while(tmp)
    {
	struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
    copy->val=tmp->val;
    copy->next=tmp->next;
    tmp->next=copy;
    tmp=copy->next;
    }
    tmp=head;
    while(tmp)
    {
        if(tmp->random == NULL)
        {
           tmp->next->random=NULL; 
        }
        else
        {
            tmp->next->random=tmp->random->next;
        }
        tmp=tmp->next->next;
    }
   struct Node*copyTail=NULL,*copyHead=NULL;
    tmp=head;
    while(tmp)
    {
        struct Node*copy=tmp->next;
        struct Node*next=copy->next;
        if(copyTail==NULL)
        {
            copyHead=copyTail=copy;
        }
        else
        {
            copyTail->next=copy;
            copyTail=copy;
        }
        tmp->next=next;
        tmp=next;
    }
    return copyHead;
     
}

 

---

到此为止，我们顺序表和链表的所有练习就结束了，下一篇文章我们专注练习栈的知识~