设有一个由正整数组成的
多(向
后)单链表,编写完成下列功能的算法：
(1) 写出单链表结点数据结构定义;
(2）若结点数值是奇数,则将其与直接后继结点的数值交换;若该数值是偶数,则将其直接后继结点删除。
该回答引用chatgpt:
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* swapAndDelete(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
while (cur->next && cur->next->next) {
if (cur->next->val % 2 == 1) {
// 奇数节点，交换节点值
ListNode* oddNode = cur->next;
ListNode* evenNode = oddNode->next;
ListNode* nextNode = evenNode->next;
evenNode->next = oddNode;
oddNode->next = nextNode;
cur->next = evenNode;
} else {
// 偶数节点，删除其后继节点
ListNode* evenNode = cur->next->next;
cur->next->next = evenNode->next;
delete evenNode;
}
cur = cur->next;
}
ListNode* newHead = dummy->next;
delete dummy;
return newHead;
}
// 测试
int main() {
// 构造链表
ListNode* head = new ListNode(1);
ListNode* cur = head;
for (int i = 2; i <= 7; i++) {
cur->next = new ListNode(i);
cur = cur->next;
}
cout << "Before swapAndDelete: ";
cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
// 调用算法
head = swapAndDelete(head);
cout << "After swapAndDelete: ";
cur = head;
while (cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
// 释放链表空间
cur = head;
while (cur) {
ListNode* tmp = cur;
cur = cur->next;
delete tmp;
}
return 0;
}
其中，swapAndDelete 函数实现了上述要求。算法首先定义了一个哑节点 dummy，并将其指向链表的头节点。然后，使用循环遍历整个链表，对于每个节点，判断其值的奇偶性，并按照要求进行交换或删除。最后，释放哑节点 dummy 的空间，返回链表的头节点。
代码中，我们使用了 C++ 的 struct 结构体定义链表节点，同时使用了 C++11 中的 nullptr 表示空指针，避免了将 NULL 作为指针常量的常规问题。
需要注意的是，在实现过程中，应该考虑各种边界条件，例如链表为空、只有一个节点、两个节点等情况，并及时释放动态分配的内存空间，避免内存泄漏
不知道你这个问题是否已经解决, 如果还没有解决的话:package com.zr.demo01;
import java.util.Arrays;
//对数组中的数从小到大排序,使用多种方法排序(冒泡排序,选择排序,快速排序)
public class Eleventh {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr=new int[] {9,8,11,54,87,6,44,3};
/*
//冒泡排序
System.out.println("冒泡排序:");
System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
bubbleSort(arr);
System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
*/
/*
//选择排序
System.out.println("选择排序:");
System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
choiceSort(arr);
System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
*/
//快速排序
System.out.println("快速排序:");
System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
quickSort(arr, 0, arr.length-1);
System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
}
/**
* 冒泡排序:相邻两个数比较
* 9 8 11 54 87 6 44 3
* 8 9 11 54 6 44 3 87 得到最大的数87,第1次循环,比较7次
* 8 9 11 6 44 3 54 87 得到倒数第二大的数54,第2次循环,比较6次
* 8 9 6 11 3 44 54 87 得到倒数第三大的数44,第3次循环,比较5次
* 8 6 9 3 11 44 54 87 得到倒数第四大的数11,第4次循环,比较4次
* 6 8 3 9 11 44 54 87 得到倒数第五大的数9,第5次循环,比较3次
* 6 3 8 9 11 44 54 87 得到倒数第六大的数8,第6次循环,比较2次
* 3 6 8 9 11 44 54 87 得到倒数第七大的数6,第7次循环,比较1次
* 一共有8个数,循环7次就可以排序完
* 这就是冒泡排序
*/
public static void bubbleSort(int[] arr) {
//循环(arr.length-1)次
for(int i=0;i<arr.length-1;i++) {
//比较(arr.length-1-i)次
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
/**
* 选择排序:选取最大的数
* 9 8 11 54 87 6 44 3
* 3 8 11 54 87 6 44 9 第1次循环,获取最小的数3,与9更换位置
* 3 6 11 54 87 8 44 9 第2次循环,获取倒数第二小的数6,与8更换位置
* 3 6 8 54 87 11 44 9 第3次循环,获取倒数第三小的数8,与11更换位置
* 3 6 8 9 87 11 44 54 第4次循环,获取倒数第四小的数9,与54更换位置
* 3 6 8 9 11 87 44 54 第5次循环,获取倒数第五小的数11,与87更换位置
* 3 6 8 9 11 44 87 54 第6次循环,获取倒数第六小的数44,与87更换位置
* 3 6 8 9 11 44 54 87 第7次循环,获取倒数第七小的数54,与87更换位置
* 一共有8个数,循环7次
* 这就是选择排序
*/
public static void choiceSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
//最小的数的下标
int k=i;
for (int j = i; j < arr.length; j++) {
//如果arr[k]不是最小数,则改变k值
if (arr[k]>arr[j]) {
k=j;
}
}
//交换数
int temp=arr[k];
arr[k]=arr[i];
arr[i]=temp;
}
}
/**
* 快速排序
* @param arr
*/
public static void quickSort(int[] arr,int start,int end) {
//如果开始下标>=结束下标,直接结束函数
if (start>=end) {
return;
}
//小下标
int low=start;
//大下标
int high=end;
//默认第一个数为关键字
int key=arr[low];
while(low<high) {
while(arr[high]>=key&&low<high) {//双保险
high--;
}
int temp1=arr[low];
arr[low]=arr[high];
arr[high]=temp1;
while(arr[low]<=key&&low<high) {//双保险
low++;
}
int temp2=arr[low];
arr[low]=arr[high];
arr[high]=temp2;
}
//对小的部分快速排序
quickSort(arr, start, low-1);
//对大的部分快速排序
quickSort(arr, high+1, end);
}
}
我可以解决这个问题。
首先定义单链表的结构体如下：
struct Node{
int val;
struct Node* next;
};
其中val表示结点的值，next表示指向下一个结点的指针。然后实现具有上述功能的算法，可以采用迭代的方法依次遍历链表，对于每个结点的值进行判断和操作。具体实现代码如下：
void swapOrDelete(struct Node* head){
struct Node* cur = head;
while(cur != NULL && cur->next != NULL){
if(cur->val % 2 != 0){
//交换cur和cur->next结点的值
int tmp = cur->val;
cur->val = cur->next->val;
cur->next->val = tmp;
}
else{
//删除cur->next结点
struct Node* del = cur->next;
cur->next = del->next;
free(del);
}
cur = cur->next;
}
}
其中head表示单链表的头结点，函数名称为swapOrDelte，具体操作包括：
实现过程中需要注意指针的操作，例如要进行结点的交换或删除，需要用到指向结点的指针。如果某个结点被删除，需要注意释放该结点所占用的内存空间。