保研机试备考三：链表操作

AcWing 66. 两个链表的第一个公共结点

题目

https://www.acwing.com/problem/content/62/

思路

一开始想着暴力做，$O(n^{2})$的遍历两个链表，发现TLE了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        ListNode *p=headA,*q;
        for(;p!=NULL;p=p->next)
        {
            for(q=headB;q!=NULL;q=q->next)
            {
                if(q==p)
                    return p;
            }
        }
        return p;
    }
};

看了y总的讲解，顿悟。

指针p从headA开始走，如果走到尾巴了，从headB开始走
指针q从headB开始走，如果走到尾巴了，从headA开始走
假设两条链表从头到第一个公共的节点的长度分别为$a$和$b$，公共的那部分长度为$l$
+ 如果$a==b$，则他们的公共节点就是第一次相遇的点，此时p走了a，q走了b
+ 如果$a!=b$，则他们的公共节点是他们再出发后的点，也是第一次相遇的点，此时p走了$a+l+b$,q走了$b+l+a$,所以无论如何都会相遇
+ 如果两条链表没有公共节点，那么他们会一起走向空节点，走的距离都是$a+b(a!=b)$，或者$a(a==b)$

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p=headA,q=headB;
        while(q!=p)
        {
            p=p?p->next:headB;
            q=q?q->next:headA;
        }
        return p;
    }
};

AcWing 3756. 筛选链表

题目

https://www.acwing.com/problem/content/3759/

思路

• 1: 两重遍历即可解决
• 2: 利用哈希表，只遍历一遍解决

代码

两重遍历：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        ListNode *p,*q,*t,*s=head;
        for(p=head;p!=NULL;p=p->next)
        {
            for(q=p,t=p->next;t!=NULL;)
            {
                if((t->val==p->val)||(t->val+p->val==0))
                {
                    q->next=t->next;
                    free(t);
                    t=q->next;
                }
                else
                {
                    q=t;
                    t=t->next;
                }
            }
        }
        return s;
    }
};

哈希表只遍历一遍：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        bool st[10010];
        memset(st,0,sizeof(st));
        st[abs(head->val)]=true;
        auto p=head->next,s=head,q=head;
        while(p)
        {
            if(st[abs(p->val)])
            {
                q->next=p->next;
                free(p);
                p=q->next;
            }
            else
            {
                st[abs(p->val)]=true;
                q=p;
                p=p->next;
            }
        }
        return s;
    }
};

AcWing 3757. 重排链表

题目

https://www.acwing.com/problem/content/3760/

思路

把要插入到前面的节点的值保存下来，往原来的链表里插就好，记得插之前把要插的点在链表里先去除掉。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        vector<int> rev;  //把要往前插的节点存下来
        ListNode *p=head,*q;
        int count=0;    //算出有多少个节点
        while(p)
        {
            rev.push_back(p->val);
            count++;
            p=p->next;
        }
        reverse(rev.begin(),rev.end());
        int pp=count-count/2;
        for(int i=0;i<pp;i++) rev.pop_back();    //去除不用往前插的节点

        auto t=head;             //在链表中把相应的尾巴去掉
        for(int i=1;i<pp;i++)
            t=t->next;
        t->next=NULL;


        p=head;                                      //开始插入节点
        for(int i=0;i<rev.size();i++)
        {
            q=(ListNode*)malloc(sizeof(ListNode));
            q->val=rev[i];
            q->next=p->next;
            p->next=q;
            p=q->next;
        }
    }
};