链表常用操作及面试题

╰+攻爆jí腚メ 2022-08-05 12:05 116阅读 0赞

链表是一种比较基础的数据结构，虽然在acm比赛中不常用，但是在面试中还是比较常问的，所以拿出来写了一下，发现很多错误，由于操作中用到很多指针，所以不经常写的话很容易写错。

这里写了一下链表的创建，比较基础！  
然后是删除链表的元素，需要考虑删除的是否为第一个元素。  
然后是找链表的倒数第k个元素，可以用两个指针，一个指针后移k次，然后两个同时向后走，当先走k次的走到尾部的时候，另一个刚好到倒数第k个元素，因为两个指针的位置一直是相差k的。  
最后是反转链表，边向后走，边把链表的指针指向前面的元素就可以了。

Notice：  
1：链表只有在创建和删除节点的时候需要分配内存，即操作内存的时候需要，这是因为链表分配内存块不是连续的，是离散的，即一个节点一个节点的分配，所以需要调用内存分配函数，内存分配函数常用的有两个  
C++中的new和C语言中的malloc这个也是面试常问的，即其区别。  
调用方法的话很简单，

ListNode *node = new ListNode();
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));

当然别忘了释放内存，其对应的delete和free，写法如下

delete node;
    free(node);

它们两个有什么区别呢？  
1:now返回指定类型的指针，其可以自动计算所要分配内存的大小。而malloc需要强制转换成实际的类型，并且大小要我们给出来。  
2：malloc只管分配内存，不对其值进行初始化，即值为随机的，而new可以初始化

一些练习代码：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    
    struct ListNode
    {
        int val;
        ListNode * next;
    };
    
    ListNode* creat(int n)  //创建链表
    {
        ListNode *head  = new ListNode(), *p = new ListNode();
       // head = p = (ListNode *)malloc(sizeof(ListNode));
        scanf("%d",&p->val);
        p->next = NULL;
        head = p;
        for(int i=1;i<n;i++)
        {
            ListNode *tmp = new ListNode();
            //tmp = (ListNode* )malloc(sizeof(ListNode));
            scanf("%d",&tmp->val);
            tmp->next = NULL;
            p->next = tmp;
            p = p->next;  ///notice：指针后移
        }
        return head;
    }
    void print(ListNode *head)   ///打印链表
    {
        while(head!=NULL){
            printf("%d ",head->val);
            head = head->next;
        }
        puts("");
    }
    
    ListNode* RemoveNode(ListNode *head,int num)
    {
        ListNode *newhead = NULL;  //只有在添加的时候才需要分配内存
        newhead = head;  ///head 指向移动之后newhead和tmp并不跟着移动
        if(newhead->val == num){  ///删除的是头结点的话
            head = head->next;
            return head;
        }
        ListNode *tmp = NULL;
        tmp = head;   //记录找到节点的前一个节点
        while(newhead!=NULL)  //其他节点
        {
            if(newhead->val == num){
                tmp->next = tmp -> next -> next;
                //delete tmp;  不能释放内存
                return head;
            }
            tmp = newhead;
            newhead = newhead->next;
        }
    }
    void Find_KthNode(ListNode *head,int k)  ///查找倒数第k个元素
    {
        ListNode *one = NULL,*two = NULL;
        one = head,two = head;
        while(one!=NULL && k--)
        {
            one = one->next;
        }
        while(one!=NULL)
        {
            one = one->next;
            two = two->next;
        }
        printf("Find last %dth secessful\n");
        printf("%d\n",two->val);
    }
    ListNode* ReverseList(ListNode *head)
    {
        ListNode *p = head;
        ListNode *pre = NULL;
        while(p!=NULL)
        {
            ListNode *tmp = p->next;
            if(tmp==NULL)
                head = p;
            p->next = pre;
            pre = p;
            p = tmp;  ///Notice : 这里写成p = p->next 是错的
        }
        return head;
    }
    
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            ListNode *head = creat(n);
            puts("Creat secessful");
            print(head);
            int num;
            scanf("%d",&num);
            head = RemoveNode(head,num);
            puts("ReMove secessful");
            print(head);
            scanf("%d",&num);
            Find_KthNode(head,num);
            head = ReverseList(head);
            //printf("HEAD->%d\n",head->val);
            print(head);
        }
        return 0;
    }
    /*****
    10
    1 2 3 4 5 6 7 8 9 10
    10
    3
    ******/