devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【追求卓越03】数据结构--链表练习题

作者：小蓝xlanll | 2024-05-07 02:37:04

赞

踩

【追求卓越03】数据结构--链表练习题

引导

        链表是我们工作和面试的中常常会遇到的知识点，只有长时间的练习和思考才能游刃有余。故总结以下几个比较经典的链表题和对应的代码，进行参考。

链表的反转

思路：

  1. 将链表遍历，将每个节点拷贝一份，之后再将所有的节点反向链接。该方法简单，但是我并不喜欢。因为空间复杂度为O(n),时间复杂度也为O(n).
  2. 利用递归，将先遍历到最后节点，再返回，将每个节点的指向上一个节点。头节点指向null。

#include<stdlib.h>
typedef struct node{
     int num;
     struct node * next;
}Node;
int insertnode(Node* head,Node* newNode)
{
        if(head == NULL)
        {
                printf("head is null,insert fail\n");
            return -1;
        }
        Node* temp = head;
        while(temp->next!= NULL)
        {
            temp = temp->next;
        }
        temp->next = newNode;
    return 0;
}
int print_list(Node* head)
{
        while(head!=NULL)
        {
            printf("%d\n",head->num);
                head = head->next;
        }
    return 0;
}
Node* rollback(Node* head)
{
        Node* temp = head->next;
        Node* newhead = NULL;
        if(temp != NULL)
        {
           newhead = rollback(temp);
        }
        else
        {
                return head;
        }
        temp->next = head;
        head->next = NULL;
    return newhead;
}
int main()
{
        Node * head = (Node*)malloc(sizeof(Node));
        head->num = 1;
        head->next = NULL;
    int i = 0;
        for(i = 2 ; i < 5 ; i ++)
        {
            Node * NewNode = (Node*)malloc(sizeof(Node));
                NewNode->num = i;
                NewNode->next = NULL;
                insertnode(head,NewNode);
        }       
        print_list(head);
        Node* Newhead = rollback(head);
        print_list(Newhead);
        return 0;
}

单向链表中环的检测

        该题，我觉得可以拓展到以下三个问题：

  1. 1.检测链表中是否存在环?
  2. 2.能够求出环的长度?
  3. 3.能否求出起始点到环入口的长度?

检测链表中是否存在环

思路：

  1. 使用快慢指针，快指针指向NULL时，则不存在环；若快指针和慢指针重合，则说明有环

#include<stdlib.h>
typedef struct node{
        int num;
        struct node * next;
}Node;
int insertnode(Node* head,Node* newNode)
{
        if(head == NULL)
        {
                printf("head is null,insert fail\n");
            return -1;
        }
        Node* temp = head;
        while(temp->next!= NULL)
        {
            temp = temp->next;
        }
        temp->next = newNode;
    return 0;
}
int print_list(Node* head)
{
        while(head!=NULL)
        {
            sleep(1);
            printf("%d\n",head->num);
            head = head->next;
        }
    return 0;
}
int ring_check(Node* head)
{
    int result = -1;
    Node* fast=head;
    Node* slow=head;
    while(fast != NULL)
    {
        if(slow->next != NULL)
        slow = slow->next;
       if(fast->next != NULL && fast->next->next != NULL)
       fast = fast->next->next;
       else
       break;
       if(slow == fast)
       {
           printf("number = %d\n",slow->num);
           result = 1;
           break;
       }
    }
    return result;
}
int main()
{
        Node * head = (Node*)malloc(sizeof(Node));
        head->num = 1;
        head->next = NULL;
        Node * temp = NULL;
        int i = 0;
        for(i = 2 ; i < 2 ; i ++)
        {
                Node * NewNode = (Node*)malloc(sizeof(Node));
                NewNode->num = i;
                NewNode->next = NULL;
                insertnode(head,NewNode);
                if(i == 14)/
*决定环的入口点*
/
                {
                        temp = NewNode;
                }
                if(i == 19)
                {
                        NewNode->next = temp;
                }
        }
        int resulte = ring_check(head);
        //print_list(head);
        if(resulte == 1)
        {
            printf("list exist ring\n");
        }
        else
        {
            printf("list don't exit ring\n");
        }
        return 0;
}

求出环的长度

思路：

  1. 建立在问题一的基础之上：
  2. 当第一次相遇之后，说明该链表存在环。
  3. 而快慢指针从一个环中同一点进行移动，下一次相遇就是链表的长度。

int ring_len(Node* head)
{
    int first = -1;
    int len = 0;
    Node* fast=head;
    Node* slow=head;
    while(fast != NULL)
    {
       if(slow->next != NULL)
       slow = slow->next;
       if(fast->next != NULL && fast->next->next != NULL)
           fast = fast->next->next;
       else
               break;
       if(first == 1)
          len ++;
       if(slow == fast)
       {
           printf("number = %d\n",slow->num);
           if(first == -1)
           {
               first = 1;
           }
           else
           break;
       }
    }
    return len;
}

计算头节点到入口点的距离

思路：
依据：快指针和慢指针相遇时，慢指针肯定还没有超过整个链表长度。而快指针应该是超过链表加上nr（n,表示正整数，r表示环的长度）
现做这样的假设：
链表的整个长度是L
头节点到入口点的距离为a
第一次相遇点距离入口点为X，并走了s步
得到以下公式：
2s -s = nr
x+a = s
可以得到a= (n-1)r + (r-x)
其中r-x表示相遇点到入口点的距离。
故：从head节点，第一次相遇节点分别出发。再次相遇肯定是入口点。

Node* ring_meet(Node* head)
{
 Node* resulte = NULL;
 Node* fast=head;
 Node* slow=head;
 while(fast != NULL)
 {
    if(slow->next != NULL)
    slow = slow->next;
       if(fast->next != NULL && fast->next->next != NULL)
           fast = fast->next->next;
       else
           return resulte;
       if(slow == fast)
       {
           printf("number = %d\n",slow->num);
           break;
       }
    }
    resulte = head;
    int len = 0;
    while(resulte != slow)
    {
        resulte= resulte->next;
        slow = slow->next;
        len++;
    }
    printf("len = %d\n",len);
    return resulte;
}

如何判断两个链表是否相交

该问题其实就是环检测的变种。只要将其中一个链表尾节点指向头节点。再检测另一条链表中是否存在环即可。

两个有序的链表合并

思路：

遍历其中一个链表，将节点与另一链表进行比较，进行插入。

Node * list_merge(Node*L1 , Node*L2)
{
    Node * head= (Node*)malloc(sizeof(Node));
    Node* cur = head;
    while(L1 != NULL && L2 != NULL)
    {
        if(L1->num <= L2->num )
        {
            cur->next = L1;
            L1 = L1->next;
        }
        else
        {
            cur->next = L2;
            L2 = L2->next;
        }
        cur=cur->next;
    }
    if(L1 == NULL)
    {
       cur->next=L2;
    }
    if(L2 == NULL)
    {
       cur->next=L1;
    }
    return head->next;
}

删除链表中指定节点

思路：

  1. 遍历链表，当遇到节点相同的，便删除对应节点。这样的事件复杂度为O(n)
  2. 将节点的下一个节点赋值为本节点，之后指向node->next->next;这个思路的时间复杂度是O(1)。但是你需要考虑节点的位置；
  3. 在链表头
  4. 在链表尾
  5. 在链表中间

int delete_node(Node* head,Node* delete)
{
    if(delete==NULL )
    {
        return 0;
    }
    if(delete->next == NULL)
    {
        /
*last node*
/
        while(head->next != delete)
        {
                head=head->next;
        }
        head->next = NULL;
        free(delete);
        return 0;
    }
    delete->num = delete->next->num;
    Node * temp = delete->next;
    delete->next = delete->next->next;
    free(temp);
    return 0;
}
平均复杂度为O(1)。

求链表中的中间节点

思路:（当链表长度为偶数，取相邻两个节点的第一个）

  1. 遍历链表，找到尾节点。并记录链表长度。再从头结点遍历，达到中间节点即可。这种方式事件复杂度为O(n),空间复杂度O(1)。但感觉太low了，并不喜欢。
  2. 使用快慢指针，当快指针达到尾节点时，慢节指针肯定是在中间节点

Node* mid_node(Node* head)
{
    if(head == NULL)
    {
        return NULL;
    }
    Node* fast=head;
    Node* slow = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

约瑟夫问题

约瑟夫问题，是我偶然看到的一个算法题。感觉很有意思，就记录下来了。

故事：

        据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

        该问题拓展很多，这里我给出的问题，有100个人，每数到3，就剔除，输出剔除顺序。

例如： 1，2，3，4，5，6

输出：3，6，4，2，5，1

思路：

        实现起来应该是很简单的，就是有N个节点的环，从头节点开始，依次数数，当数到3时，就将节点删除，一直重复到只有一个节点。

int Joseph(Node* head)
{
    int i = 1;
    if(head ==NULL)
    {
         printf("list is empty\n");
    }
    while(head->next != head)
    {
        i++;
        if(i%3 == 0)
        {
             i=1;
             Node* temp = head->next;
             head->next = head->next->next;
             printf("%d\n",temp->num);
             free(temp);
        }
        head=head->next;
    }
    printf("last is %d\n",head->num);
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/547043
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号