devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

链表OJ

作者：爱喝兽奶帝天荒 | 2024-08-07 06:57:50

赞

踩

链表OJ

GDUFE 

在期末前再刷一次链表题  ~

203. 移除链表元素 - 力扣（LeetCode）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. struct ListNode* removeElements(struct ListNode* head, int val) {
  9.     struct ListNode* cur = head;
  10.     struct ListNode*prev = NULL;
  11.     while(cur){
  12.         if(cur->val == val){
  13.             if(cur==head){//头删
  14.                 cur=head->next;
  15.                 free(head);
  16.                 head= cur;
  17.             }else{
  18.                 prev->next = cur->next;
  19.                 free(cur);
  20.                 cur = prev->next;
  21.             }
  22.         }
  23.         else{
  24.             //找到val值对应的地址(遍历链表)
  25.             prev = cur;
  26.             cur=cur->next;
  27.         }
  28.     }
  29.     return head;
  30. }

206. 反转链表 - 力扣（LeetCode）

  1. struct ListNode* reverseList(struct ListNode* head) {
  2.     //记录前中后三个位置
  3.     struct ListNode*prev = NULL;
  4.     struct ListNode*cur = head;
  5.     while(cur != NULL){
  6.         struct Listndoe*nextnode = cur->next;
  7.         cur->next = prev;
  8.         prev = cur;
  9.         cur= nextnode;
  10.         
  11.     }
  12.     head = prev;
  13.     return head;
  14. }

876. 链表的中间结点 - 力扣（LeetCode）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. struct ListNode* middleNode(struct ListNode* head) {
  9.     struct ListNode* cur = head;
  10.     struct ListNdoe* mid = NULL;
  11.     int count = 0;
  12.     while(cur){
  13.         cur = cur->next;
  14.         count++;
  15.     }
  16.     int n = (count/2);//n为几就需要头删几个
  17.     while(n-->0){
  18.         mid = head->next;
  19.         free(head);
  20.         head = mid;
  21.     }
  22.     return head;
  23. }

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
  9.     struct ListNode*phead = head;//这个变量用于求出链表结点个数
  10.     struct ListNode* m = head;
  11.     struct ListNode* prev = NULL;
  12.     int count = 1,i = 0;
  13.     while(phead!=NULL){
  14.         phead = phead->next;
  15.         count++;
  16.     }
  17.     while(i++<count-n-1){//找到倒数第n个节点
  18.         prev = m;
  19.         m = m->next;
  20.     }
  21.     if(m==head){//头删
  22.         head = m->next;
  23.         free(m);
  24.         m = NULL;
  25.     }
  26.     else{//中间删除
  27.         prev->next = m->next;
  28.         free(m);
  29.         m=NULL;
  30.     }
  31.     return head;
  32. }

21. 合并两个有序链表 - 力扣（LeetCode）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
  9.  
  10.  
  11.     //若这个地方不判断list是否为空指针,后面部分对tail解引用会报错为空指针解引用
  12.     if(list1==NULL){
  13.         return list2;
  14.     }
  15.     if(list2==NULL){
  16.         return list1;
  17.     }
  18.  
  19.  
  20.  
  21.     struct ListNode*n1 = list1;
  22.     struct ListNode*n2 = list2;
  23.     struct ListNode*head = NULL;
  24.     struct ListNode*tail = NULL;//tail随时跟随新链表变动
  25.     while(n1&&n2){
  26.         if(n1->val >= n2->val){
  27.             if(head==NULL){//head最开始为NULL,要先赋值
  28.                 head = n2;
  29.                 tail = n2;
  30.             }else{
  31.                 tail->next = n2;
  32.                 tail = n2;
  33.                 //tail不断往前走,这样就可以不用每次都遍历链表找到尾再插入
  34.             }
  35.             n2 = n2->next;
  36.         }else if(n1->val < n2->val){
  37.             if(head==NULL){
  38.                 head = n1;
  39.                 tail = n1;
  40.             }else{
  41.                 tail->next = n1;
  42.                 tail = n1;
  43.             }
  44.             n1 = n1->next;
  45.         }
  46.     }
  47.     if(n2){//当n1或者n2其中一空就会跳出来判断
  48.         tail->next = n2;
  49.     }else if(n1){
  50.         tail->next = n1;
  51.     }
  52.     return head;
  53. }

现在有一链表的头指针ListNode* pHead,给一定值x,编写一段代码将所有小于x的节点都排在其余点之前,且不改变原来的数据顺序,返回重新排列后的链表头指针

面试题 02.04. 分割链表 - 力扣（LeetCode）

创建两个带哨兵的链表 然后一大放比x大的 一个放比x小的  

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode partition(ListNode head, int x) {
  11.         ListNode smlDummy = new ListNode(0),bigDummy = new ListNode(0);
  12.         ListNode sml = smlDummy,big = bigDummy;
  13.         while(head!=null){
  14.             if(head.val<x){
  15.                 sml.next = head;
  16.                 sml = sml.next;
  17.             }else{
  18.                 big.next = head;
  19.                 big = big.next;
  20.             }
  21.             head = head.next;
  22.         }
  23.         sml.next = bigDummy.next;
  24.         big.next = null;
  25.         return smlDummy.next;
  26.     }
  27. }

234. 回文链表 - 力扣（LeetCode）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. bool isPalindrome(struct ListNode* head) {
  9.     struct ListNode*n = head;
  10.     struct ListNode*m = head;
  11.     while(m && m->next){//找到中间的节点的新方法,这个地方循环后中间节点为n,可以自己画图验证
  12.         n = n->next;
  13.         m = m->next->next;
  14.     }//n为中间结点
  15.     struct ListNode*cur = n;
  16.     struct ListNode*prev =NULL;
  17.     struct ListNode*next = n->next;
  18.     while(cur){//反转链表
  19.         cur->next = prev;
  20.         prev = cur;
  21.         cur = next;
  22.         if(next){
  23.             next = next->next;
  24.         }
  25.  
  26.     }//prev 为反转后的头
  27.     struct ListNode*phead = head;
  28.     while(phead&&prev){//比较两个链表,当一个链表为NULL的时候就停止
  29.         if(phead->val!=prev->val){
  30.             return false;
  31.         }else{
  32.             phead= phead->next;
  33.             prev = prev->next;
  34.         }
  35.     }
  36.     return true;
  37. }

160. 相交链表 - 力扣（LeetCode）

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode A =headA,B = headB;
  4.         while(A!=B){
  5.             A = A!=null?A.next:headB;
  6.             B =B!=null?B.next:headA;
  7.         }
  8.         return A;
  9.     }
  10. }

将两个递增的有序链表合并为一个递增的有序链表.要求结果链表仍使用原来两个链表的存储空间
不另外占用其他的存储空间.表中不允许有重复的数据. 

  1. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  2.  
  3. /*
  6. 思路:La,Lb是工作指针 当La和Lb所指向的元素值不同的时候,较小的值链接到Lc上
  7. La和Lb所指向的元素值相同的时候,将La的值链接到Lc上,Lb上的删掉
  8. */
  9. #include <iostream>
  10. using namespace std;
  11. // 定义链表结点结构
  12. struct ListNode {
  13.     int data;
  14.     ListNode *next;
  15. };
  16.  
  17. // 定义链表头指针类型
  18. typedef ListNode* LinkList;
  19.  
  20. // 合并两个有序链表
  21. void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) 
  22. {
  23.     ListNode *pa = La->next; // La 的工作指针，初始化为第一个结点
  24.     ListNode *pb = Lb->next; // Lb 的工作指针，初始化为第一个结点
  25.     Lc = La; // 用 La 的头结点作为 Lc 的头结点
  26.     ListNode *pc = Lc; // Lc 的工作指针
  27.  
  28.     while (pa && pb) {
  29.         if (pa->data < pb->data) {
  30.             pc->next = pa; // 将 pa 链接在 pc 的后面
  31.             pc = pa; // pc 指针后移
  32.             pa = pa->next; // pa 指针后移
  33.         } else if (pa->data > pb->data) {
  34.             pc->next = pb; // 将 pb 链接在 pc 的后面
  35.             pc = pb; // pc 指针后移
  36.             pb = pb->next; // pb 指针后移
  37.         } else { // 相等时取 La 中的元素，删除 Lb 中的元素
  38.             pc->next = pa; // 将 pa 链接在 pc 的后面
  39.             pc = pa; // pc 指针后移
  40.             pa = pa->next; // pa 指针后移
  41.             ListNode *q = pb->next; // 保存 pb 的下一个结点
  42.             delete pb; // 删除 pb 结点
  43.             pb = q; // pb 指针后移
  44.         }
  45.     }
  46.  
  47.     // 插入剩余段
  48.     pc->next = pa ? pa : pb;
  49.  
  50.     // 释放 Lb 的头结点
  51.     delete Lb;
  52. }
  53.  
  54. int main() {
  55.     // 测试代码
  56.     // 创建两个链表 La 和 Lb，并初始化它们
  57.     LinkList La = new ListNode();
  58.     La->next = NULL;
  59.     LinkList Lb = new ListNode();
  60.     Lb->next = NULL;
  61.  
  62.     // 填充链表 La
  63.     ListNode *p = La;
  64.     for (int i = 1; i <= 5; i += 2) {
  65.         ListNode *node = new ListNode();
  66.         node->data = i;
  67.         node->next = NULL;
  68.         p->next = node;
  69.         p = node;
  70.     }
  71.  
  72.     // 填充链表 Lb
  73.     p = Lb;
  74.     for (int i = 2; i <= 6; i += 2) {
  75.         ListNode *node = new ListNode();
  76.         node->data = i;
  77.         node->next = NULL;
  78.         p->next = node;
  79.         p = node;
  80.     }
  81.  
  82.     // 打印合并前的链表
  83.     std::cout << "La: ";
  84.     for (p = La->next; p != NULL; p = p->next)
  85.         std::cout << p->data << " ";
  86.     std::cout << "\nLb: ";
  87.     for (p = Lb->next; p != NULL; p = p->next)
  88.         std::cout << p->data << " ";
  89.     std::cout << "\n";
  90.  
  91.     // 合并链表
  92.     LinkList Lc;
  93.     MergeList(La, Lb, Lc);
  94.  
  95.     // 打印合并后的链表
  96.     std::cout << "Lc: ";
  97.     for (p = Lc->next; p != NULL; p = p->next)
  98.         std::cout << p->data << " ";
  99.     std::cout << "\n";
  100.  
  101.     // 释放链表
  102.     p = Lc;
  103.     while (p != NULL) {
  104.         ListNode *q = p->next;
  105.         delete p;
  106.         p = q;
  107.     }
  108.  
  109.     return 0;
  110. }

//3）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出 A 与 B
//的交集，并存放于 A 链表中。
//[题目分析]
//只有同时出现在两集合中的元素才出现在结果表中, 合并后的新表使用头指针 Lc 指向。
//pa 和 pb 分别是链表 La 和 Lb 的工作指针, 初始化为相应链表的第一个结点， 从第一个结点开
//始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，如果两个表中相等的元素时，摘取
//La 表中的元素，删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的
//元素，此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点，为空时，依次删除另一
//个非空表中的所有元素。
//

  1.  
  2.  
  3. #include <iostream>
  4.  
  5. struct Node {
  6.     int data;      // 数据
  7.     Node* next;    // 指向下一个节点的指针
  8.  
  9.     // 构造函数
  10.     Node(int val) : data(val), next(nullptr) {}
  11. };
  12.  
  13. typedef Node* LinkList; // 定义链表类型
  14.  
  15. void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) {
  16.     Node* pa = La->next;  // 指向链表 La 的当前节点
  17.     Node* pb = Lb->next;  // 指向链表 Lb 的当前节点
  18.     Node* pc = La;        // Lc 的工作指针，初始化为 La 的头结点
  19.     Node* u;              // 用于暂存要删除的节点
  20.     Lc = La;
  21.     while (pa && pb) {
  22.         if (pa->data == pb->data) { // 如果两个节点数据相等（交集部分）
  23.             pc->next = pa;         // 将当前节点接入结果链表
  24.             pc = pa;               // pc 指向新接入的节点
  25.             pa = pa->next;         // pa 向后移动
  26.             u = pb;                // 暂存要删除的节点 pb
  27.             pb = pb->next;         // pb 向后移动
  28.             delete u;              // 删除节点 pb
  29.         }
  30.         else if (pa->data < pb->data) {
  31.             u = pa;                // 暂存要删除的节点 pa
  32.             pa = pa->next;         // pa 向后移动
  33.             delete u;              // 删除节点 pa
  34.         }
  35.         else {
  36.             u = pb;                // 暂存要删除的节点 pb
  37.             pb = pb->next;         // pb 向后移动
  38.             delete u;              // 删除节点 pb
  39.         }
  40.     }
  41.  
  42.     // 处理剩余的节点
  43.     while (pa) {
  44.         u = pa;                    // 暂存要删除的节点 pa
  45.         pa = pa->next;             // pa 向后移动
  46.         delete u;                  // 删除节点 pa
  47.     }
  48.     while (pb) {
  49.         u = pb;                    // 暂存要删除的节点 pb
  50.         pb = pb->next;             // pb 向后移动
  51.         delete u;                  // 删除节点 pb
  52.     }
  53.  
  54.     pc->next = NULL;            // 置链表尾标记
  55.  
  56.     delete Lb;                     // 释放 Lb 的头结点
  57. }

（ 4）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出两个集
合 A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合） ，并以同样的形
式存储，同时返回该集合的元素个数。
[ 题目分析 ]
求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素，即删除链表中的相应结
点 , 所以要保存待删除结点的前驱，使用指针 pre 指向前驱结点。 pa 和 pb 分别是链表 La 和
Lb 的工作指针 , 初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表
La 和 Lb 均为到达表尾结点时，如果 La 表中的元素小于 Lb 表中的元素， pre 置为 La 表的工
作指针 pa 删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，
此表的工作指针后移。 当链表 La 和 Lb 有一个为空时， 依次删除另一个非空表中的所有元素.

  1. *
  2. 将两个非递减的有序链表合并为一个非递增的有序链表。 要求结果链表仍使用原来
  3. 两个链表的存储空间 , 不另外占用其它的存储空间。表中允许有重复的数据。
  4.  
  5. [ 题目分析 ]
  6. 合并后的新表使用头指针 Lc 指向， pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为
  7. 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结
  8. 点时，依次摘取其中较小者重新链接在 Lc 表的表头结点之后，如果两个表中的元素相等，只
  9. 摘取 La 表中的元素，保留 Lb 表中的元素。当一个表到达表尾结点，为空时，将非空表的剩
  10. 余元素依次摘取，链接在 Lc 表的表头结点之后。
  11.  
  12. */
  13. #include <iostream>
  14. using namespace std;
  15. void Difference(LinkList& La, LinkList& Lb, int *n) {
  16.     Node *pa = La->next;  // 指向链表 La 的当前节点
  17.     Node *pb = Lb->next;  // 指向链表 Lb 的当前节点
  18.     Node *pre = La;       // pre 为 La 中 pa 所指结点的前驱结点的指针
  19.     Node *u;              // 用于暂存要删除的节点
  20.  
  21.     *n = 0;  // 初始化结果集合中元素个数为 0
  22.  
  23.     while (pa && pb) {
  24.         if (pa->data < pb->data) {
  25.             pre = pa;     // A 链表中当前结点指针后移
  26.             pa = pa->next;
  27.             (*n)++;       // 计数器加一，表示找到一个差集元素
  28.         } else if (pa->data > pb->data) {
  29.             pb = pb->next; // B 链表中当前结点指针后移
  30.         } else { // pa->data == pb->data，即 A 和 B 中当前结点数据相同
  31.             pre->next = pa->next;  // 删除 A 中当前结点
  32.             u = pa;
  33.             pa = pa->next;
  34.             delete u;  // 释放结点空间
  35.         }
  36.     }
  37.  
  38.     // 处理 A 中剩余的节点，这些节点都是 A 中独有的元素
  39.     while (pa) {
  40.         u = pa;         // 暂存要删除的节点 pa
  41.         pa = pa->next;  // pa 向后移动
  42.         delete u;       // 删除节点 pa
  43.         (*n)++;         // 计数器加一，表示找到一个差集元素
  44.     }
  45.  
  46.     // 由于 B 中剩余的节点都是不会出现在 A 中的元素，无需处理
  47.  
  48.     pre->next = nullptr;  // 置链表尾标记
  49.  
  50.     // 释放 Lb 的头结点
  51.     delete Lb;
  52. }

5）设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C，其中 B
表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于零的结点（链表 A 中的元素为非零整数，要求 B、 C 表利用 A 表的结点） 。

[ 题目分析 ]
B 表的头结点使用原来 A 表的头结点，为 C 表新申请一个头结点。从 A 表的第一个结点
开始，依次取其每个结点 p，判断结点 p 的值是否小于 0，利用前插法，将小于 0 的结点插入B 表 , 大于等于 0 的结点插入 C 表。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 定义链表结点结构
  5. typedef struct Node {
  6.     int data;
  7.     struct Node *next;
  8. } Node;
  9.  
  10. // 创建新结点
  11. Node* createNode(int data) {
  12.     Node *newNode = (Node *)malloc(sizeof(Node));
  13.     if (!newNode) {
  14.         printf("内存分配失败\n");
  15.         exit(1);
  16.     }
  17.     newNode->data = data;
  18.     newNode->next = NULL;
  19.     return newNode;
  20. }
  21.  
  22. // 打印链表
  23. void printList(Node *head) {
  24.     Node *current = head->next;  // 跳过头结点
  25.     while (current != NULL) {
  26.         printf("%d -> ", current->data);
  27.         current = current->next;
  28.     }
  29.     printf("NULL\n");
  30. }
  31.  
  32. // 释放链表内存
  33. void freeList(Node *head) {
  34.     Node *current = head;
  35.     Node *next;
  36.     while (current != NULL) {
  37.         next = current->next;
  38.         free(current);
  39.         current = next;
  40.     }
  41. }
  42.  
  43. // 分解链表
  44. void splitList(Node *A, Node *B, Node *C) {
  45.     Node *current = A->next;  // 跳过头结点
  46.     Node *tailB = B;  // B 表的尾指针
  47.     Node *tailC = C;  // C 表的尾指针
  48.  
  49.     while (current != NULL) {
  50.         if (current->data < 0) {
  51.             tailB->next = current;
  52.             tailB = current;
  53.         } else if (current->data > 0) {
  54.             tailC->next = current;
  55.             tailC = current;
  56.         }
  57.         current = current->next;
  58.     }
  59.  
  60.     // 断开 B 和 C 表的最后一个结点
  61.     tailB->next = NULL;
  62.     tailC->next = NULL;
  63. }
  64.  
  65. int main() {
  66.     // 初始化链表 A
  67.     Node *A = createNode(0);  // 带头结点
  68.     Node *current = A;
  69.     int values[] = {3, -1, 5, -2, 8, -6, 7};  // 示例数据
  70.     for (int i = 0; i < sizeof(values)/sizeof(values[0]); i++) {
  71.         current->next = createNode(values[i]);
  72.         current = current->next;
  73.     }
  74.  
  75.     printf("链表 A: ");
  76.     printList(A);
  77.  
  78.     // 初始化链表 B 和 C 的头结点
  79.     Node *B = createNode(0);  // 带头结点
  80.     Node *C = createNode(0);  // 带头结点
  81.  
  82.     // 分解链表
  83.     splitList(A, B, C);
  84.  
  85.     printf("链表 B: ");
  86.     printList(B);
  87.  
  88.     printf("链表 C: ");
  89.     printList(C);
  90.  
  91.     // 释放链表内存
  92.     freeList(A);
  93.     freeList(B);
  94.     freeList(C);
  95.  
  96.     return 0;
  97. }

（ 6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

  1. //（ 6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
  2.  
  3. #include <iostream>
  4. #include <climits>
  5.  
  6. struct ListNode {
  7.     int value;
  8.     ListNode* next;
  9.     ListNode(int x) : value(x), next(NULL) {}
  10. };
  11.  
  12. ListNode* findMaxNode(ListNode* head) {
  13.     if (!head) {
  14.         return NULL;
  15.     }
  16.  
  17.     ListNode* max_value_node = head;
  18.     ListNode* current = head->next;
  19.  
  20.     while (current) {
  21.         if (current->value > max_value_node->value) {
  22.             max_value_node = current;
  23.         }
  24.         current = current->next;
  25.     }
  26.  
  27.     return max_value_node;
  28. }
  29.  
  30. int main() {
  31.     // 创建一个链表用于测试
  32.     ListNode* node5 = new ListNode(3);
  33.     ListNode* node4 = new ListNode(1);
  34.     node4->next = node5;
  35.     ListNode* node3 = new ListNode(4);
  36.     node3->next = node4;
  37.     ListNode* node2 = new ListNode(2);
  38.     node2->next = node3;
  39.     ListNode* head = new ListNode(5);
  40.     head->next = node2;
  41.  
  42.     // 调用函数并输出结果
  43.     ListNode* max_node = findMaxNode(head);
  44.     if (max_node) {
  45.         std::cout << "最大值节点的值是: " << max_node->value << std::endl;
  46.     } else {
  47.         std::cout << "链表为空" << std::endl;
  48.     }
  49.  
  50.     // 释放分配的内存
  51.     delete node5;
  52.     delete node4;
  53.     delete node3;
  54.     delete node2;
  55.     delete head;
  56.  
  57.     return 0;
  58. }

（ 7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的
存储空间。

  1. // 逆转链表
  2. #include<iostream>
  3. using namespace std;
  4. struct ListNode{
  5. 	int value;
  6. 	ListNode* next;
  7. 	ListNode(int x=0):value(x),next(NULL){}
  8. }; 
  9.  
  10. ListNode*reverseList(ListNode*head) {
  11. 	ListNode*prev = NULL;
  12. 	ListNode* current = head;
  13. 	
  14. 	while(current){
  15. 		ListNode*next = current->next;//保存当前节点的下一个节点
  16. 		current->next = prev;//反转当前节点指针;
  17. 		prev = current;//更新prev为当前节点
  18. 		current = next;//移动到下一个节点 
  19. 	}
  20. 	return prev;//prev现在是新的头结点 
  21. }
  22.  
  23. int main()
  24. {
  25. 	//创建一个链表用于测试
  26. 	ListNode*node5 = new ListNode(5);
  27. 	ListNode*node4 = new ListNode(4);
  28. 	node4->next = node5;
  29. 	ListNode*node3 = new ListNode(3);
  30. 	node3->next = node4;
  31. 	ListNode* node2 = new ListNode(2);
  32. 	node2->next = node3;
  33. 	ListNode*head = new ListNode(1);
  34. 	head->next = node2;
  35. 	
  36. 	//打印原链表
  37. 	cout<<"原链表:";
  38. 	ListNode*temp = head;
  39. 	while(temp){
  40. 		cout<<temp->value<<" ";
  41. 		temp = temp->next; 
  42. 	} 
  43. 	cout<<endl;
  44. 	
  45. 	
  46. 	///调用函数反转链表
  47. 	ListNode*new_head = reverseList(head);
  48. 	
  49. 	//打印反转后的链表
  50. 	cout<<"反转后的链表:";
  51. 	temp = new_head;
  52. 	while(temp){
  53. 		cout<<temp->value<<" ";
  54. 		temp = temp->next;
  55. 	} 
  56. 	cout<<endl;
  57. 	
  58. 	//释放分配的内存
  59. 	delete node5;
  60. 	delete node4;
  61. 	delete node3;
  62. 	delete node2;
  63. 	delete head;
  64. 	
  65. 	return 0; 
  66.  }

 （ 8）设计一个算法，删除递增有序链表中值大于 mink 且小于 maxk 的所有元素（ mink
和 maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。

  1. #include <iostream>
  2.  
  3. struct ListNode {
  4.     int value;
  5.     ListNode* next;
  6.     ListNode(int x) : value(x), next(nullptr) {}
  7. };
  8.  
  9. ListNode* removeElementsInRange(ListNode* head, int mink, int maxk) {
  10.     // 创建哨兵节点
  11.     ListNode* dummy = new ListNode(0);
  12.     dummy->next = head;
  13.     ListNode* prev = dummy;
  14.     ListNode* current = head;
  15.  
  16.     while (current) {
  17.         if (current->value > mink && current->value < maxk) {
  18.             prev->next = current->next; // 跳过当前节点
  19.         } else {
  20.             prev = current; // 继续遍历
  21.         }
  22.         current = current->next; // 移动到下一个节点
  23.     }
  24.  
  25.     // 更新头节点
  26.     ListNode* new_head = dummy->next;
  27.     delete dummy; // 释放哨兵节点的内存
  28.     return new_head;
  29. }
  30.  
  31. int main() {
  32.     // 创建一个递增有序链表用于测试
  33.     ListNode* node5 = new ListNode(6);
  34.     ListNode* node4 = new ListNode(5);
  35.     node4->next = node5;
  36.     ListNode* node3 = new ListNode(4);
  37.     node3->next = node4;
  38.     ListNode* node2 = new ListNode(3);
  39.     node2->next = node3;
  40.     ListNode* head = new ListNode(1);
  41.     head->next = node2;
  42.  
  43.     int mink = 2;
  44.     int maxk = 5;
  45.  
  46.     // 打印原链表
  47.     std::cout << "原链表: ";
  48.     ListNode* temp = head;
  49.     while (temp) {
  50.         std::cout << temp->value << " ";
  51.         temp = temp->next;
  52.     }
  53.     std::cout << std::endl;
  54.  
  55.     // 调用函数删除指定范围的元素
  56.     ListNode* new_head = removeElementsInRange(head, mink, maxk);
  57.  
  58.     // 打印删除后的链表
  59.     std::cout << "删除后的链表: ";
  60.     temp = new_head;
  61.     while (temp) {
  62.         std::cout << temp->value << " ";
  63.         temp = temp->next;
  64.     }
  65.     std::cout << std::endl;
  66.  
  67.     // 释放分配的内存
  68.     delete node5;
  69.     delete node4;
  70.     delete node3;
  71.     delete node2;
  72.     delete head;
  73.  
  74.     return 0;
  75. }

（ 9）已知 p 指向双向循环链表中的一个结点， 其结点结构为 data 、prior 、next 三个域，
写出算法 change, 交换 p 所指向的结点和它的前缀结点的顺序。

  1. #include <iostream>
  2.  
  3. struct ListNode {
  4.     int data;
  5.     ListNode* prior;
  6.     ListNode* next;
  7.     ListNode(int x) : data(x), prior(nullptr), next(nullptr) {}
  8. };
  9.  
  10. void change(ListNode* p) {
  11.     if (p == nullptr || p->prior == nullptr) {
  12.         return; // 无法交换
  13.     }
  14.  
  15.     ListNode* Q = p->prior; // Q 是 p 的前驱节点
  16.     ListNode* Q_prior = Q->prior; // Q 的前驱节点
  17.     ListNode* P_next = p->next; // P 的后继节点
  18.  
  19.     // 交换 P 和 Q 的指针
  20.     if (Q_prior != nullptr) {
  21.         Q_prior->next = p;
  22.     }
  23.     if (P_next != nullptr) {
  24.         P_next->prior = Q;
  25.     }
  26.  
  27.     p->prior = Q_prior;
  28.     p->next = Q;
  29.     Q->prior = p;
  30.     Q->next = P_next;
  31. }
  32.  
  33. void printList(ListNode* head) {
  34.     ListNode* temp = head;
  35.     do {
  36.         std::cout << temp->data << " ";
  37.         temp = temp->next;
  38.     } while (temp != head);
  39.     std::cout << std::endl;
  40. }
  41.  
  42. int main() {
  43.     // 创建一个双向循环链表用于测试
  44.     ListNode* node1 = new ListNode(1);
  45.     ListNode* node2 = new ListNode(2);
  46.     ListNode* node3 = new ListNode(3);
  47.     ListNode* node4 = new ListNode(4);
  48.  
  49.     node1->next = node2; node1->prior = node4;
  50.     node2->next = node3; node2->prior = node1;
  51.     node3->next = node4; node3->prior = node2;
  52.     node4->next = node1; node4->prior = node3;
  53.  
  54.     ListNode* head = node1;
  55.  
  56.     // 打印原链表
  57.     std::cout << "原链表: ";
  58.     printList(head);
  59.  
  60.     // 调用函数交换 node3 和 node2
  61.     change(node3);
  62.  
  63.     // 打印交换后的链表
  64.     std::cout << "交换后的链表: ";
  65.     printList(head);
  66.  
  67.     // 释放分配的内存
  68.     delete node1;
  69.     delete node2;
  70.     delete node3;
  71.     delete node4;
  72.  
  73.     return 0;
  74. }

（ 10）已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n) 、空间复
杂度为 O(1) 的算法，该算法删除线性表中所有值为 item 的数据元素。

  1. #include <iostream>
  2.  
  3. void removeItem(int* A, int& n, int item) {
  4.     int j = 0; // j 指向下一个保留的位置
  5.  
  6.     for (int i = 0; i < n; ++i) {
  7.         if (A[i] != item) {
  8.             A[j] = A[i];
  9.             ++j;
  10.         }
  11.     }
  12.  
  13.     // 更新数组长度
  14.     n = j;
  15. }
  16.  
  17. int main() {
  18.     // 测试数据
  19.     int A[] = {1, 2, 3, 2, 4, 2, 5};
  20.     int n = sizeof(A) / sizeof(A[0]);
  21.     int item = 2;
  22.  
  23.     std::cout << "原数组: ";
  24.     for (int i = 0; i < n; ++i) {
  25.         std::cout << A[i] << " ";
  26.     }
  27.     std::cout << std::endl;
  28.  
  29.     // 删除所有值为 item 的元素
  30.     removeItem(A, n, item);
  31.  
  32.     std::cout << "删除后的数组: ";
  33.     for (int i = 0; i < n; ++i) {
  34.         std::cout << A[i] << " ";
  35.     }
  36.     std::cout << std::endl;
  37.  
  38.     return 0;
  39. }

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

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

  

闽ICP备14008679号