考研机试-链表

作者： 作者的头像   Y_Y_Y ,  2023-03-19 14:36:05 ,  所有人可见 ,  阅读 46

0


单链表

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node{
    int val;
    Node * next;
    Node():next(NULL){};  //使用构造函数初始化列表
    Node(int _val): val(_val),next(NULL){};  //只要写一个val值不空的构造函数，next值一定要为空。
};

void print(Node * head)
{
    for(auto p = head;p;p = p->next)
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}

int main()
{
    Node * head = new Node(1); //head不是第一个节点，而是指向第一个结点的指针,他的值就是第一个结点的地址。

    Node * a = new Node(2); //新建的链表2的next值仍然为空。
    head -> next = a;
    Node * b = new Node(3);//在2后面加入3
    a -> next = b;

    Node * c = new Node(4);//在头节点后面插入4,下面两步顺序不能变
    c -> next = head->next;
    head->next = c;

    //删除2号节点
    c -> next = a -> next;
    delete(a);

    //删除头节点,一定要先将头节点存到p中
    auto p = head;
    head = head->next;
    delete(p);//一定要删除头节点

    print(head);
    return 0;
}

双链表

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node{
    int val;
    Node * next, * prev;
    Node():next(NULL),prev(NULL){};  //使用构造函数初始化列表
    Node(int _val): val(_val),next(NULL),prev(NULL){};  //只要写一个val值不空的构造函数，next值一定要为空。
};

void print(Node * head)
{
    for(auto p = head;p;p = p->next)
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}

int main()
{
    //初始化双链表，需要定义两个护法，防止出界
    Node * head = new Node(), * tail = new Node();
    head -> next = tail,tail -> prev = head;

    //在头节点后面添加一个新的节点
    Node * a = new Node(1);
    a -> next = head -> next;
    a -> prev = head;
    //一下这两句表示将原来的地址指回当前的地址，千万不能写反。
    head->next->prev = a;
    head -> next = a;

    print(head); //0 1 0

    //在a后面插入一个b
    Node * b = new Node(2);
    b -> next = a -> next;
    b->prev = a;
    a -> next -> prev = b;
    a -> next = b;

    print(head); //0 1 2 0

    //删除b(只能使用b这个节点)
    b -> prev -> next = b -> next;
    b -> next -> prev = b -> prev;
    print(head); //0 1 0

    return 0;
}

循环双链表

//循环双链表，就是左右护法只能是同一个节点，并且要修改一下遍历，一下只对与双链表的不同之处做了注释:
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node{
    int val;
    Node * next, * prev;
    Node():next(NULL),prev(NULL){};  //使用构造函数初始化列表
    Node(int _val): val(_val),next(NULL),prev(NULL){};  //只要写一个val值不空的构造函数，next值一定要为空。
};

void print(Node * head)
{
    for(auto p = head->next;p!=head;p = p->next) // ！！！！！遍历时要修改！！！！！
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}

int main()
{
    //初始化双链表，需要定义两个护法，防止出界
    Node * head = new Node(), * tail = head;  //!!!!head = tail,就是这两个指针的值相同 !!!!!
    head -> next = tail,tail -> prev = head;

    //在头节点后面添加一个新的节点
    Node * a = new Node(1);
    a -> next = head -> next;
    a -> prev = head;
    //一下这两句表示将原来的地址指回当前的地址，千万不能写反。
    head->next->prev = a;
    head -> next = a;

    print(head); //1 !!!!两边的哨兵都不会被用到!!!!

    //在a后面插入一个b
    Node * b = new Node(2);
    b -> next = a -> next;
    b->prev = a;
    a -> next -> prev = b;
    a -> next = b;

    print(head); //1 2

    //删除b(只能使用b这个节点)
    b -> prev -> next = b -> next;
    b -> next -> prev = b -> prev;
    print(head); //1

    return 0;
}

两个链表的第一个公共节点

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

/**
 * 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 = headB;
        while(p != q)
        {
            if(p) p = p->next;
            else p = headB;
            if(q) q = q->next;
            else q = headA;
        }

        return q;
    }
};

筛选链表

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

/**
 * 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]={0};
        ListNode * dummy = new ListNode(0);
        dummy -> next = head;  //这一步可千万不要忘了!!!!!!
        for(auto p = dummy;p->next != NULL;)  //要删掉一个节点必须找到该结点的前一个结点的地址,所以这里要判断p->next。
        {
            if(st[abs(p->next->val)]) 
            {
                //删除链表的p->next这个节点
                auto q = p->next;
                p->next = p->next->next;
                delete(q); //！！！ 易错 ！！！由于这里p->next的值已经改变了，所以不能直接写delete(p->next),
                            //而是要事先用q将p->next存起来，然后delete(q)
            }
            else
            {
                st[abs(p->next->val)] = true;
                p = p->next;
            }
        }
        return head;
    }
};

重排链表

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) {
    //!!!!!!! 易错:!!!!!! [1]的时候,b = a->next就是空了，不可能再有c = b->next了。
        if (!head->next) return;  //边界条件:如果只有一个节点，直接return .
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        int left = (n + 1) / 2;  // 前半段的节点数(把奇数多出来的那个节点算到了前面)
        auto a = head;
        for (int i = 0; i < left - 1; i ++ ) a = a->next; //a走到了左边的最后一个节点
        auto b = a->next, c = b->next;  //b是第二段的尾节点，c是第二段的倒数第二个节点

        a->next = b->next = NULL; //前一段的后一段的尾部节点分别指向NULL
        //反转第二段链表，当c==NULL时，b正好走到了头节点
        while (c) {
            auto p = c->next;  
            c->next = b;
            b = c, c = p;
        }
        //合并两段链表
        for (auto p = head, q = b; q;) {  //由于第一个链表比第二个链表多1个，所以这里要写q
            auto o = q->next;  //总结经验，先写下面的代码，然后再看哪些值是被修改的，要保留下来。
            // 将第二个链表的节点插入到第一个链表的结点的后面
            q->next = p->next;
            p->next = q;
            //移动两个链表的节点
            p = p->next->next;
            q = o;
        }
    }
};

0 评论