BL12. 翻转链表
描述
对于一个链表 L: L0→L1→…→Ln-1→Ln,
将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…
输入是一串数字，请将其转换成单链表格式之后，再进行操作
输入描述
一串数字，用逗号分隔输出描述
一串数字，用逗号分隔示例1
输入:
1,2,3,4,5
输出:
1,5,2,4,3
C++ 解法, 执行用时: 9ms, 内存消耗: 1776KB, 提交时间: 2020-12-23
#include <bits/stdc++.h>
using namespace std;
int change(string s)
{
int len=s.size();
int num=0;
for(int i=0;i<len;i++)
{
num=(num*10+(s[i]-'0'));
}
return num;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
vector<int> a,b,c;
string s,temp; cin>>s;
int len=s.size();
for(int i=0;i<len;i++)
{
if(s[i]==',') {a.push_back(change(temp)); temp="";}
else temp+=s[i];
if(i==len-1) a.push_back(change(temp));
}
len=a.size();
//cout<<len<<endl;
for(int i=1;i<=(len-1)/2;i++) b.push_back(a[i]);
for(int i=(len-1)/2+1;i<len;i++) c.push_back(a[i]);
reverse(c.begin(),c.end());
cout<<a[0]<<(len==1 ? "\n" : ",");
int indexb=0,indexc=0;
for(int i=1;i<len;i++)
{
if(i%2==0) cout<<b[indexb++];
else cout<<c[indexc++];
cout<<(i==len-1 ? "\n" : ",");
}
return 0;
}
C 解法, 执行用时: 12ms, 内存消耗: 816KB, 提交时间: 2021-09-19
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node{
int elem;
struct Node *next;
}SNode,*SLinketList;
#define NODESIZE sizeof(struct Node)
SLinketList slinket_list_create(void){
struct Node* head = (struct Node*)malloc(NODESIZE);
if(head==NULL){
return NULL;
}
head->next = NULL;
return head;
}
void slinket_list_insert_back(SLinketList head,int elem){
struct Node *last = head;
while(last->next!=NULL){
last = last->next;
}
struct Node *node = (struct Node *)malloc(NODESIZE);
node->elem = elem;
node->next = NULL;
last->next = node;
}
int slinket_list_size(SLinketList head){
int size = 0;
struct Node *node = head->next;//head指向头结点 head->next指向第一个结点
while(node != NULL){
size++;
node = node->next;//让node指针指向下一个节点
}
return size;
}
void slinket_list_reverse(SLinketList head){
if(head->next == NULL || head->next->next == NULL){
return;
}
struct Node *prev = NULL;
struct Node *curr = head->next;
struct Node *next = NULL;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
}
void slinket_list_reset_seq(SLinketList head){
int size = slinket_list_size(head);
if(size<=2)
return;
int i;
struct Node *node = head->next;
for(i=0;i<size/2;i++){
node = node->next;
}
slinket_list_reverse(node);
struct Node *front = node->next, *back = head->next;
node->next = NULL;
node = head;
bool flag = true;
while(front!=NULL && back!=NULL){
node->next = back;
back = back->next;
node = node->next;
node->next = front;
front = front->next;
node = node->next;
}
node->next = back;
}
void print(int num){
printf(",%d",num);
}
void slinket_list_travel(SLinketList head,void (*travel)(int)){
struct Node *node = head->next;
while(node!=NULL){
travel(node->elem);
node = node->next;
}
}
int main()
{
SLinketList list=slinket_list_create();
int n;
/*while(scanf("%d,",&n)!=EOF)
{
slinket_list_insert_back(list,n);
}*/
int i=0,a[100000];
SLinketList node=list->next;
for (i=0;i<100000;i++)
{
scanf("%d",&a[i]);
if (getchar() == '\n')
{
break;
}
}
int l=i,j;
for (i=0,j=l;i<(l+1)/2;i++,j--)
{
printf("%d,",a[i]);
if ((i==j)||(i+1==j))
{
break;
}
printf("%d,",a[j]);
}
printf("%d", a[j]);
return 0;
}
C++ 解法, 执行用时: 12ms, 内存消耗: 1692KB, 提交时间: 2020-10-29
//https://www.nowcoder.com/question/next?pid=16518829&qid=362298&tid=36970309
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define be(x) begin(x), end(x)
ostream_iterator<int> out(cout, ",");
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("/mnt/c/users/wang-/source/repos/linux_vs/linux_vs/ao_ben_in1", "r", stdin);
//freopen("/home/wqs/projects/linux_vs/huan_ju_in1", "r", stdin);
vi arr, reverse_arr;
int i = 1;
arr.emplace_back(0);
int temp;
char tmp;
while (cin >> temp)
{ arr.emplace_back(temp);
cin.ignore();// default sizwe is 1;
//scanf("%c", &tmp);
//cin >> tmp;
}
auto len = arr.size();
if(len%2==0){
for(int i=1; i<len/2; ++i)
{
reverse_arr.emplace_back(arr[i]);
reverse_arr.emplace_back(arr[len-i]);
}
reverse_arr.emplace_back(arr[len / 2 ]);
}
else {
for(int i=1; i<=len/2; ++i)
{
reverse_arr.emplace_back(arr[i]);
reverse_arr.emplace_back(arr[len-i]);
}
}
copy(begin(reverse_arr),end(reverse_arr)-1, out);
cout << reverse_arr.back();
//copy(be(reverse_arr), out);
//reverse_arr
return 0;
}
C 解法, 执行用时: 13ms, 内存消耗: 760KB, 提交时间: 2021-05-10
#include<stdio.h>
int main() {
int i, a[100000];
for (i = 0; i < 100000; i++) {
scanf("%d", &a[i]);
if (getchar() == '\n') {
break;
}
}
int l = i, j;
for (i = 0, j = l; i < (l + 1) / 2; i++, j--) {
printf("%d,",a[i]);
if ((i == j) || (i + 1 == j)) {
break;
}
printf("%d,", a[j]);
}
printf("%d", a[j]);
return 0;
}
C++ 解法, 执行用时: 13ms, 内存消耗: 1720KB, 提交时间: 2020-10-29
//https://www.nowcoder.com/question/next?pid=16518829&qid=362298&tid=36970309
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define be(x) begin(x), end(x)
ostream_iterator<int> out(cout, ",");
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("/mnt/c/users/wang-/source/repos/linux_vs/linux_vs/ao_ben_in1", "r", stdin);
//freopen("/home/wqs/projects/linux_vs/huan_ju_in1", "r", stdin);
vi arr, reverse_arr;
int i = 1;
arr.emplace_back(0);
int temp;
char tmp;
while (cin >> temp)
{ arr.emplace_back(temp);
cin.ignore();// default sizwe is 1;
//scanf("%c", &tmp);
//cin >> tmp;
}
auto len = arr.size();
if(len%2==0){
for(int i=1; i<len/2; ++i)
{
reverse_arr.emplace_back(arr[i]);
reverse_arr.emplace_back(arr[len-i]);
}
reverse_arr.emplace_back(arr[len / 2 ]);
}
else {
for(int i=1; i<=len/2; ++i)
{
reverse_arr.emplace_back(arr[i]);
reverse_arr.emplace_back(arr[len-i]);
}
}
copy(begin(reverse_arr),end(reverse_arr)-1, out);
cout << reverse_arr.back();
//copy(be(reverse_arr), out);
//reverse_arr
return 0;
}