前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法(五)——链表相关算法题目

数据结构与算法(五)——链表相关算法题目

作者头像
拉维
发布2022-03-28 09:18:15
7680
发布2022-03-28 09:18:15
举报
文章被收录于专栏:iOS小生活

前面几篇文章主要是讲了线性表,线性表是四种逻辑结构(集合结构、线性结构、树结构、图结构)的一种任何一种逻辑结构,都是通过两种物理结构(顺序存储、链式存储)来在内存中实现的,线性表也不例外。在前面的几篇文章中,我们既讲了线性表的顺序存储,也讲了线性表的链式存储。在线性表的链式存储中,我们又细分了单向链表、单向循环链表、双向链表、双向循环链表。如下图所示:

顺序存储最大的优势就是可以快速读取指定位置的元素,它的弊端是做增删的时候后面的元素都需要移位;链式存储最大的优势是它做增删很迅速,只需要改变指针域的指向即可,其劣势是每一次查找都需要遍历

今天我们这篇文章,就是通过几道题目,来巩固一下对线性表的理解。话不多说,直接开干。

本篇文章中的所有涉及到链表的题目,都是使用的单项链表。关于单向链表的创建、打印和插入的代码如下:

代码语言:javascript
复制
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;

// 数据类型
typedef int ElementType;

// 节点结构
typedef struct Node{
  ElementType data; // 数据域
  struct Node *next; // 指针域
} Node;

// 链表类型
typedef struct Node * LinkedList;

// 创建一个带有头结点的单向链表
Status createLinkedList(LinkedList *list) {
  // 新建节点
  LinkedList headNode = malloc(sizeof(Node));
  if (!headNode) {
    return  Error;
  }
  headNode->data = -1;
  headNode->next = NULL;

  // 将新节点设置为链表的头结点
  *list = headNode;
  return Success;
}

// 打印链表
Status printLinkedList(LinkedList list) {
  if (!list) {
    printf("该链表不存在\n");
    return  Error;
  }

  LinkedList node = list->next;
  if (!node) {
    printf("该链表为空\n");
    return Success;
  }

  printf("链表信息如下:\n");
  while (node) {
    printf("%d\n", node->data);
    node = node->next;
  }
  return Success;
}

// 往单链表中插入元素
Status insertElement(LinkedList *list, int index, ElementType element) {
  // 如果链表为空则直接报错
  if (!(*list)) {
    return  Error;
  }

  // 校验坐标的有效性
  if (index < 1) {
    return Error;
  }

  // 找到待插入位置前面的节点(如果待插入位置超过链表长度,则直接插入到链表尾部)
  LinkedList priorNode = *list;
  for (int i = 1; i < index && priorNode->next; i++, priorNode = priorNode->next);

  // 新建节点
  LinkedList node = malloc(sizeof(Node));
  node->data = element;

  // 找到在当前待插入位置上的节点
  LinkedList nextNode = priorNode->next;

  // 将新节点加入到链表中
  node->next = nextNode;
  priorNode->next = node;

  return  Success;
}

题目一

题目1:

将两个递增的有序链表合并为一个有序链表。要求:结果链表仍然使用两个链表的存储空间,不再另外占用其他的链表空间;并且表中不能有重复数据。

题目分析:

(1)两个链表均是有序递增的,因此对两条链表进行一次遍历即可

(2)最终合成的链表中不能有重复的数据,因此要及时移除重复项

(3)要求不额外占用空间,意思就是不能建立新的节点,因此要在原链表上进行操作

(4)生成的新的链表是一个有序链表,它没有说是有序递增还是有序递减。如果是有序递增,则则使用后插法;如果是有序递减,则使用前插法。

逻辑设计:

(1)两个待合并的递增的有序链表是listA和listB,使用listC来记录结果链表,让listC复用listA的头结点,并使用elementC来记录listC的最后一个节点

(2)同时循环遍历listA和listB,并分别使用elementA和elementB来记录当前遍历到的节点。然后让elementC的指针域指向数值较小的那个节点;如果数值相等,则让elementC的指针域指向其中一个节点,并注意移除另外一个节点

(3)当遍历完其中一条链表的时候会跳出循环,因此还要将剩下那条链表中的元素依次拼接到listC上面

(4)释放listB的头结点

代码如下:

代码语言:javascript
复制
void mergeLists(LinkedList listA, LinkedList listB, LinkedList *resultList) {
  // 复用链表A的头结点
  LinkedList listC = listA;
  // 记录结果链表中的最后一个节点
  LinkedList tailNodeC = listC;

  // 自头结点开始遍历链表A和链表B
  LinkedList nodeA = listA->next;
  LinkedList nodeB = listB->next;
  while (nodeA && nodeB) {
    if (nodeA->data < nodeB->data) {
      tailNodeC->next = nodeA;
      tailNodeC = nodeA; // taiNodeC是记录的结果链表中的最后一个节点
      nodeA = nodeA->next;
    } else if (nodeB->data < nodeA->data) {
      tailNodeC->next = nodeB;
      tailNodeC = nodeB;
      nodeB = nodeB->next;
    } else {
      // 当链表中元素相等的时候,只取用其中一个,其余的都销毁
      tailNodeC->next = nodeA;
      tailNodeC = nodeA;
      nodeA = nodeA->next;

      // 销毁另外一个节点
      LinkedList tempNode = nodeB;
      nodeB = nodeB->next;
      free(tempNode);
    }
  }

  // 将余下的节点拼接到结果链表上
  if (nodeA) {
    tailNodeC->next = nodeA;
  }

  if (nodeB) {
    tailNodeC->next = nodeB;
  }

  // 释放链表B的头结点
  free(listB);

  *resultList = listC;
}

验证代码如下:

代码语言:javascript
复制
 LinkedList listA;
  LinkedList listB;

  createLinkedList(&listA);
  createLinkedList(&listB);

  for (int i = 1; i < 10; i++) {
    insertElement(&listA, i, 2*i);
  }

  for (int i = 1; i < 10; i++) {
    insertElement(&listB, i, 3*i);
  }

  printLinkedList(listA);
  printLinkedList(listB);

  LinkedList listC;
  mergeLists(listA, listB, &listC);
  printLinkedList(listC);

题目二

题目2:

已知两个链表A和B分别表示两个集合,其元素递增排列。请设计一个算法,用于求出A和B的交集,并存储在A链表中。

题目分析:

(1)A和B两个链表都是有序递增的,所以可以直接遍历一遍即可

(2)求交集,意思是找到相同的元素,然后保留其中一个节点,其他的节点都释放

(3)最终的结果存在A链表中,说明需要复用链表A的头结点

逻辑设计:

(1)链表A、B分别使用listA、listB来表示,交集使用listC来表示

(2)将listC的头结点设置为listA的头结点,并且使用临时变量tailNodeC来表示listC的最后一个节点

(3)遍历listA和listB,找到值相等的节点,然后tailNodeC的指针域指向其中一个节点,另一个销毁,并且注意更新tailNodeC的指向;其他的较小的节点也销毁

(4)直到有一条链表到头了,那么就跳出循环,然后将剩余的那条链表中的元素都给销毁

(5)将交集链表的尾结点的指针域置空,并且将链表B的头结点销毁

代码如下:

代码语言:javascript
复制
void interSectionOf(LinkedList listA, LinkedList listB, LinkedList *resultList) {
  // 交集链表复用链表A的头结点
  LinkedList listC = listA;

  // 记录交集链表中的最后一个节点
  LinkedList tailNodeC = listC;

  // 循环遍历链表A和B
  LinkedList nodeA = listA->next;
  LinkedList nodeB = listB->next;
  LinkedList tempNode;
  while (nodeA && nodeB) {
    // 销毁值较小的节点
    if (nodeA->data < nodeB->data) {
      tempNode = nodeA;
      nodeA = nodeA->next;
      free(tempNode);
    } else if (nodeB->data < nodeA->data) {
      tempNode = nodeB;
      nodeB = nodeB->next;
      free(tempNode);
    } else {
      //如果值相等,则保留其中一个节点,另外一个节点销毁
      tailNodeC->next = nodeA;
      tailNodeC = nodeA; // 更新交集链表的尾结点
      nodeA = nodeA->next;

      tempNode = nodeB;
      nodeB = nodeB->next;
      free(tempNode);
    }
  }

  // 当其中一条链表遍历完的时候跳出循环,然后将余下的那条链表中的剩余节点都清空
  while (nodeA) {
    tempNode = nodeA;
    nodeA = nodeA->next;
    free(tempNode);
  }

  while (nodeB) {
    tempNode = nodeB;
    nodeB = nodeB->next;
    free(tempNode);
  }

  //将交集链表的尾结点的指针域置空
  tailNodeC->next = NULL;

  // 销毁链表B的头结点
  free(listB);

  *resultList = listC;
}

验证代码如下:

代码语言:javascript
复制
  LinkedList listA;
  LinkedList listB;

  createLinkedList(&listA);
  createLinkedList(&listB);

  for (int i = 1; i < 10; i++) {
    insertElement(&listA, i, 2*i);
  }

  for (int i = 1; i < 10; i++) {
    insertElement(&listB, i, 3*i);
  }

  printLinkedList(listA);
  printLinkedList(listB);

  LinkedList listC;
  interSectionOf(listA, listB, &listC);
  printLinkedList(listC);

题目三

题目3:

将链表中的所有节点的链接方向”原地旋转“,要求只能利用原表的存储空间。

例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};

题目分析:

(1)只能利用原表的存储空间,说明不能开辟新的节点,但是可以新增临时的指针变量

(2)初步想法是,通过一个临时指针变量来记录原链表的节点,然后遍历原链表,依次将遍历到的节点插入到原链表首元结点的位置(前插法)。

(3)其实,原地旋转也就是所谓的逆序,而链表的前插法就是第一个插入进来的节点最终会置于链表的最后,这也是所谓的逆序。原地旋转、逆序、前插法这几个词是对应的。

逻辑设计:

(1)新建一个节点指针变量tempNode,并让其指向原链表的首元结点

(2)通过tempNode来遍历链表

(3)将每一次遍历的节点都插入到原链表首元结点的位置(前插法),注意修改该节点的后继节点

代码如下:

代码语言:javascript
复制
void reverseLinkedList(LinkedList *list) {
  // 记录原链表的首元节点
  LinkedList currentNode = (*list)->next;
  LinkedList tempNode;

  // 将原链表的头结点与其他节点断开
  (*list)->next = NULL;

  // 自首元结点开始遍历原链表
  while (currentNode) {
    // 将当前遍历到的节点插入到首元结点的位置
    tempNode = currentNode->next;
    currentNode->next = (*list)->next;
    (*list)->next = currentNode;
    // 更新遍历的节点位置
    currentNode = tempNode;
  }
}

验证代码如下:

代码语言:javascript
复制
  LinkedList listA;

  createLinkedList(&listA);

  for (int i = 1; i < 10; i++) {
    insertElement(&listA, i, 2*i);
  }

  printLinkedList(listA);

  reverseLinkedList(&listA);
  printLinkedList(listA);

题目四

题目4:

设计一个算法,删除递增有序链表中值大于等于min且小于等于max(min、max是给定的两个参数,其值可以与表中的元素相同,也可以不同)的所有元素。

题目分析:

(1)该链表是递增有序链表,因此可以直接遍历找到符合范围的两个边界节点

(2)将两个边界节点通过指针域连接起来

(3)依次遍历销毁两个边界节点之间的各个节点

逻辑设计:

(1)通过两个遍历,分别找到值大于等于min的第一个节点前面的那个节点priorNode,以及值小于等于max的最后那个节点tailNode

(2)找到priorNode的后继节点(即待移除的第一个节点),并使用变量toDeleteHeadNode来记录

(3)将priorNode的后继设置为tailNode的后继

(4)依次遍历移除toDeleteHeadNode和tailNode之间的所有节点

代码如下:

代码语言:javascript
复制
void removeNodesBetween(LinkedList *list, int min, int max) {
  // 检验输入范围的有效性
  if (min > max) {
    return;
  }

  // 如果链表元素为空,则直接返回
  if (!(*list) || !(*list)->next) {
    return;
  }

  LinkedList priorNode = *list;
  LinkedList toDeleteHeadNode;
  LinkedList toDeleteTailNode = (*list)->next;

  // 寻找第一个大于等于min的节点之前的那个节点
  while ((priorNode->next) && (priorNode->next->data < min)) {
    priorNode = priorNode->next;
  }

  // 获取待删除的第一个节点
  toDeleteHeadNode = priorNode->next;

  // 寻找最后一个小于等于max的节点
  while ((toDeleteTailNode->next) && (toDeleteTailNode->next->data <= max)) {
    toDeleteTailNode = toDeleteTailNode->next;
  }

  // 验证寻找到的边界节点
  if (toDeleteHeadNode->data < min || toDeleteTailNode->data > max) {
    return;
  }

  // 连接两个边界节点
  priorNode->next = toDeleteTailNode->next;

  // 依次释放待删除节点
  LinkedList tempNode;
  while (toDeleteHeadNode != toDeleteTailNode) {
    tempNode = toDeleteHeadNode;
    toDeleteHeadNode = toDeleteHeadNode->next;
    free(tempNode);
  }
}

上述算法的时间复杂度是O(n),空间复杂度是O(1)。其中,n是链表长度。

验证代码如下:

代码语言:javascript
复制
  LinkedList listA;

  createLinkedList(&listA);

  for (int i = 1; i < 10; i++) {
    insertElement(&listA, i, 2*i);
  }

  printLinkedList(listA);

  removeNodesBetween(&listA, 0,1);
  printLinkedList(listA);

题目五

题目5:

假设将n(n>1)个整数存放到一维数组R中,请设计一个在时间和空间两方面都尽可能高效的算法,

将R中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,......,xn-1)变换为(xp,xp+1,...,xn-1,x0,x1,...,xp-1).

题目分析:

例如: array[10] = {0,1,2,3,4,5,6,7,8,9},

n = 10,p = 3;

pre[10] = {3,4,5,6,7,8,9,0,1,2}

这里考察的是线性表的顺序存储。

逻辑设计:

(1)先将原数组完全翻转

(2)再将翻转后的数组通过位置分成两段进行翻转

(3)将顺序表的翻转算法抽离出来,抽离的时候需要暴露出翻转的初始位置和结束位置

代码如下:

代码语言:javascript
复制
// 数组中某个范围内的元素翻转
void reverseDecequenceList(int *list, int start, int end) {
  int left = start;
  int right = end;

  int temp;
  while (left < right) {
    // 交换
    temp = list[left];
    list[left] = list[right];
    list[right] = temp;

    left++;
    right--;
  }
}

void transport(int *list, int listLength, int index) {
  // 如果左移的位置超过数组长度,或者左移小于等于0位,那么就直接退出本次函数执行
  if (index >= listLength || index <= 0) {
    return;
  }

  // 先将整个数组翻转
  reverseDecequenceList(list, 0, listLength-1);

  // 分段翻转
  reverseDecequenceList(list, 0, listLength-index-1);
  reverseDecequenceList(list, listLength-index, listLength-1);
}

上述算法的时间复杂度是O(n),空间复杂度是O(1)。其中,n是数组长度。

验证代码如下:

代码语言:javascript
复制
  int listA[9] = {1,2,3,4,5,6,7,8,9};
  transport(listA, 9, 3);
  for (int i = 0; i < 9; i++) {
    printf("%d", listA[i]);
  }

题目六

题目6:

已知一个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

题目分析:

(1)本题目就是在一个数组中去寻找主元素,也就是说,找到个数占数组长度一半以上的元素并输出,如果没有找到的话则输出-1。

(2)设计算法的时候,可以让一个主元素跟一个非主元素配对,最后没有其他元素与之匹配的那些元素就是主元素

逻辑设计:

(1)通过变量mainElement来记录主元素,通过count来记录主元素与其他非主元素抵消之后剩余的个数

(2)自数组中第1个元素开始循环遍历数组,在每一次循环体中执行的逻辑如下

①如果count==0,则设置当前遍历到的值为mainElement,并且设置count为1

②如果count>0,如果当前遍历到的值与mainElement相等,则count加1

③如果count>0,如果当前遍历到的值与mainElement不相等,则count减1

(3)遍历完之后,如果count大于0,则拿到mainElement,再循环遍历一遍来获取到mainElement出现的次数,如果该次数大于数组总长度的一般,那么就为主元素。

代码如下:

代码语言:javascript
复制
int getMainElement(int *list, int listLength){
  // 使用mainElement来记录主元素的值
  int mainElement = -1;
  int count = 0;

  // 找到主元素,以及主元素与非主元素的个数差
  int currentValue;
  for (int i = 0; i < listLength; i++) {
    currentValue = list[i];
    if (count > 0) {
      currentValue == mainElement ? count++ : count--;
    } else {
      mainElement = currentValue;
      count = 1;
    }
  }

  // 当个数差为零的时候说明没有主元素
  if (count <= 0) {
    return -1;
  }

  // 重新遍历,以获取mainElement在数组中真正出现的次数
  count = 0;
  for (int i = 0; i < listLength; i++) {
    list[i] != mainElement ?: count++;
  }

  // 只有当出现次数大于一半的时候才会是主元素,否则不是主元素
  if (count > listLength/2) {
    return mainElement;
  } else {
    return -1;
  }
}

上述算法的时间复杂度是O(listLength),空间复杂度是O(1)。其中,listLength是数组的长度。

验证代码如下:

代码语言:javascript
复制
  int list[10] = {1,2,6,6,6,6,6,3,4,5};
  printf("%d", getMainElement(list, 11));

题目七

题目7:

用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};

题目分析:

(1)本题要求时间复杂度尽可能高,这意味着我们可以利用空间换时间,也就是说只要能保证时间复杂度高,那么空间复杂度是不需要考虑的

(2)由于|data|<=n,所以可以创建一个长度为n+1的数组,数组的元素初始值均设置为0,该数组用于记录单链表中的节点值的绝对值出现的频次

逻辑设计:

(1)假设单链表是linkedList,链表长度是m,要求链表中的数值的绝对值都不能大于n

(2)创建一个长度为n+1的一位数组array,利用该数组的index表示linkedList中的各个节点上的值的绝对值,array各个位置上的初始值均设置为0,这样就表示各个值暂时均未出现过

(3)自首元结点开始遍历,获取到遍历到的节点的值的绝对值currentValue,然后找到array[currentValue]的值,如果该值为0,则将该值设置为1,然后进行下一次遍历;如果该值为1,则将当前节点销毁,然后遍历下一节点。

(4)在上面遍历的过程中,要注意调整销毁节点以及其前驱结点的后继。

代码如下:

代码语言:javascript
复制
void filterLinkedList(LinkedList *list, int limitedValue) {
  // 链表为空的时候直接返回
  if (!(*list) || !(*list)->next) {
    return;
  }

  // 新建数组array,并初始化所有元素值为0,以记录链表节点绝对值出现的次数
  int array[limitedValue + 1];
  for (int i = 0; i < limitedValue + 1; i++) {
    array[i] = 0;
  }

  LinkedList node = *list;
  LinkedList tempNode;
  while (node->next) {
    int currentValue = abs(node->next->data);
    int flag = array[currentValue];
    if (flag == 0) {
      // 该节点上的值之前没出现过,则标记一下
      array[currentValue] = 1;
      node = node->next;
    } else {
      // 该节点上的值之前出现过,则从链表中移除该节点,并释放该节点的内存
      tempNode = node->next;
      node->next = node->next->next;
      free(tempNode);
    }
  }
}

上述代码的时间复杂度是O(m),空间复杂度是O(limitedValue)。其中m指的是链表的长度,limitedValue指的是链表中各节点值的绝对值的最大值。

验证代码如下:

代码语言:javascript
复制
  LinkedList listA;

  createLinkedList(&listA);

  insertElement(&listA, 1, -10);
  insertElement(&listA, 2, 8);
  insertElement(&listA, 3, -6);
  insertElement(&listA, 4, 4);
  insertElement(&listA, 5, -2);
  insertElement(&listA, 6, 0);
  insertElement(&listA, 7, 2);
  insertElement(&listA, 8, -4);
  insertElement(&listA, 9, 6);
  insertElement(&listA, 10, -8);

  printLinkedList(listA);

  filterLinkedList(&listA, 10);
  printLinkedList(listA);

以上。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-03-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 iOS小生活 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档