[编程题]遍历链表
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()){
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
Arrays.sort(a);
for (int i : a) System.out.print(i+" ");
}
}
}
发表于 2020-03-18 19:32:36
回复(0)
用带头结点的链表插入比较方便。
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *insert(node *head,int t)
{
node *pre=head; //pre指示前序结点
node *n=pre->next;
while(n!=NULL)
{
if(n->data<t)
{
pre=n;
n=n->next;
}
else break;
}
node *ins=(node *)malloc(sizeof(node));
ins->data=t;
pre->next=ins;
ins->next=n;
return head;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
node *head=(node *)malloc(sizeof(node));
head->next=NULL;
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
head=insert(head,t);
}
while(head->next!=NULL)
{
printf("%d ",head->next->data);
head=head->next;
}
printf("\n");
}
}
编辑于 2020-03-19 11:54:59
回复(0)
/** \没说不可以用辅助空间，那就先排序后赋值 * * \param * \param * \return * */ #include <iostream> #include <algorithm> using namespace std; struct LNode{ LNode* next=nullptr; int value; }; LNode* create_link(LNode* head,int a[],int n); void print_link(LNode* head); int main(){ int n; cin>>n; LNode* head=new LNode; int* arr=new int[n]; for(int i=0;i<n;++i) cin>>arr[i]; sort(arr,arr+n); print_link(create_link(head,arr,n)); return 0; } LNode* create_link(LNode* head,int a[],int n){ LNode* node=new LNode; head->next=node; LNode* p=node; for(int i=0;i<n;++i){ p->value=a[i]; LNode* node=new LNode; p->next=node; p=p->next; } return head; } void print_link(LNode* head){ LNode *p=head->next; while(p->next!=nullptr){ cout<<p->value<<' '; p=p->next; } delete p; }
编辑于 2020-03-09 21:30:42
回复(0)
#include <iostream>
#include <memory>
using namespace std;
struct node{
int data;
shared_ptr<node> next;
node():data(0),next(nullptr){}
node(const int& d):data(d),next(nullptr){}
};
typedef shared_ptr<node> list;
//带头节点的链表插入排序；
void insert_sort(list& l,const int& d){
list no = make_shared<node>(d);//待插入节点
list pre = l;//前驱
list now = l->next;//当前节点
while (now != nullptr && now->data <d){//找到插入位置
pre = now;
now = now->next;
}
//插入
no->next = now;
pre->next = no;
}
void print(const list& l){//打印
list now = l->next;
if(now != nullptr) cout<<now->data;
now = now->next;
while (now != nullptr){
cout<<' '<<now->data;
now = now->next;
}
cout<<endl;
}
int main(){
int n;
int a;
while(cin>>n){
list my_list = make_shared<node>();
for(int i=0;i<n;i++){
cin>>a;
insert_sort(my_list,a);
}
print(my_list);
}
return 0;
} 插入排序，智能指针应用
编辑于 2020-03-05 11:24:31
回复(0)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
int n, arr[1001];
while(scanf("%d", &n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d", &arr[i]);
}
sort(arr, arr+n);
for(int i=0;i<n;i++){
if(i==n-1) cout<<arr[i]<<endl;
else
cout<<arr[i]<<" ";
}
}
}
发表于 2018-03-19 15:39:35
回复(0)
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define maxn 1000
using namespace std;
struct node{
int data;
node* next;
};
node* create(int a[],int n)
{
node *p,*pre,*head;
head=new node;
head->next=NULL;
pre=head;
for(int i=0;i<n;++i)
{
p=new node;
p->data=a[i];
p->next=NULL;
pre->next=p;
pre=p;
}
return head;
}
int main()
{
int n,a[maxn];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
sort(a,a+n);
node* p=new node;
node* L=create(a,n);
L=L->next;
int flag=0;
while(L)
{
if(flag==0)
{
printf("%d",L->data);
flag=1;
}
else
printf(" %d",L->data);
L=L->next;
}
printf("\n");
}
return 0;
}
#include<algorithm>
#include<stdlib.h>
#define maxn 1000
using namespace std;
struct node{
int data;
node* next;
};
node* create(int a[],int n)
{
node *p,*pre,*head;
head=new node;
head->next=NULL;
pre=head;
for(int i=0;i<n;++i)
{
p=new node;
p->data=a[i];
p->next=NULL;
pre->next=p;
pre=p;
}
return head;
}
int main()
{
int n,a[maxn];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
sort(a,a+n);
node* p=new node;
node* L=create(a,n);
L=L->next;
int flag=0;
while(L)
{
if(flag==0)
{
printf("%d",L->data);
flag=1;
}
else
printf(" %d",L->data);
L=L->next;
}
printf("\n");
}
return 0;
}
发表于 2018-03-06 19:35:26
回复(0)
#include <cstdio>
#include <climits>
struct node
{
int data;
node *next;
node(int n) : data(n), next(NULL) {};
};
void insert(node *&head, int num)
{
node *pre_p = head;
node *p = pre_p->next;
while (p)
{
if (p->data > num)
{
break;
}
p = p->next;
pre_p = pre_p->next;
}
pre_p->next = new node(num);
if (p != NULL)
{
pre_p->next->next = p;
}
}
void print_list(node *&head)
{
node *p = head->next;
while (true)
{
printf("%d ", p->data);
p = p->next;
if (p->next == NULL)
{
break;
}
}
printf("%d\n", p->data);
}
void del_list(node *&head)
{
node *p = head;
while (p)
{
node *t = p;
p = p->next;
delete t;
}
}
int main()
{
int n, num;
node *head;
while (scanf("%d", &n) != EOF)
{
head = new node(INT_MIN);
for (int i = 0; i < n; i++)
{
scanf("%d", &num);
insert(head, num);
}
print_list(head);
del_list(head);
}
return 0;
}
发表于 2017-06-03 17:58:11
回复(1)
while(fscanf(STDIN,"%d",$input)){
$input_array = explode(" ",trim(fgets(STDIN)));
sort($input_array);
echo implode(" ",$input_array)."\n";
}
发表于 2017-04-10 23:31:34
回复(1)
#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
int data;
struct LNode* next;
}LNode,*list;
list InitList(){
list L;
L=(LNode*)malloc(sizeof(LNode));
L->next=NULL;
return L;
}
void insert(LNode* L,int n){
LNode *p;
p=L->next;
list pre=L;
list q;
while(p){
if(p->data<n){
pre=p;
p=p->next;
}
else break;
}
q=(LNode*)malloc(sizeof(LNode));
q->data=n;
pre->next=q;
q->next=p;
}
void print(list L){
list p=L->next;
while(p->next){
printf("%d ",p->data);
p=p->next;
}
printf("%d",p->data);
}
int main(){
int n,arr[1001];
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
list L;
L=InitList();
for(int i=0;i<n;i++){
insert(L,arr[i]);
}
print(L);
free(L);
}
return 0;
}
发表于 2018-02-23 02:31:55
回复(4)
#include<stdio.h>
#include<malloc.h>
int main()
{
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*linklist;
int a[1000],N,n,j,t;
while(scanf("%d",&N)!=EOF)
{
for(n=0;n<N;n++)
scanf("%d",&a[n]);
for(n=0;n<N;n++)
for(j=0;j<N-n-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
LNode *p,*q,*s;
p=(linklist)malloc(sizeof(LNode));
q=p;
n=0;
while(n<N)
{
s=(linklist)malloc(sizeof(LNode));
s->data=a[n];
p->next=s;
p=s;
n++;
}
p->next=NULL;
while(q->next->next!=NULL)
{
printf("%d ",q->next->data);
p=q->next;
q->next=q->next->next;
free(p);
}
printf("%d\n",q->next->data);
p=q->next;
q->next=q->next->next;
free(p);
free(q);
}
return 0;
}
#include<malloc.h>
int main()
{
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*linklist;
int a[1000],N,n,j,t;
while(scanf("%d",&N)!=EOF)
{
for(n=0;n<N;n++)
scanf("%d",&a[n]);
for(n=0;n<N;n++)
for(j=0;j<N-n-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
LNode *p,*q,*s;
p=(linklist)malloc(sizeof(LNode));
q=p;
n=0;
while(n<N)
{
s=(linklist)malloc(sizeof(LNode));
s->data=a[n];
p->next=s;
p=s;
n++;
}
p->next=NULL;
while(q->next->next!=NULL)
{
printf("%d ",q->next->data);
p=q->next;
q->next=q->next->next;
free(p);
}
printf("%d\n",q->next->data);
p=q->next;
q->next=q->next->next;
free(p);
free(q);
}
return 0;
}
发表于 2017-12-31 13:58:05
回复(0)
//建立升序链表
#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode{
int data;
struct LinkNode *next;
}LinkNode,*LinkList;
int flag;
void Insert(LinkList phead,int data){
LinkList pn = phead->next;
LinkList pre = phead;
LinkList tmp =(LinkList)malloc(sizeof(LinkList));
tmp->data = data;
tmp->next = NULL;
//寻找插入点 1位于链中 2位于链尾
while(pn && pn->data<data){
pre = pn;
pn=pn->next;
}
tmp->next = pn;
pre->next = tmp;
}
void travel(LinkList phead){
LinkList pn = phead->next;
while(pn){
if(!flag){
printf("%d",pn->data);
flag = 1;
}else printf(" %d",pn->data);
pn=pn->next;
}
}
int main(){
int num,data;
LinkList phead=(LinkList)malloc(sizeof(LinkList));
while(scanf("%d",&num)!=EOF){
flag=0;
phead->next = NULL;
phead->data = num;
for(int i=0;i<num;i++){
scanf("%d",&data);
Insert(phead,data);
}
travel(phead);
printf("\n");
}
return 0;
}
发表于 2017-02-06 19:53:02
回复(0)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct LNode{
int data;
struct LNode* next;
}LNode;
/* 尾插法创建 带头节点单链表 */
LNode * CreateList(LNode *L,int n){
int x;
L=(LNode*)malloc(sizeof(LNode)); //建立头结点
LNode *s,*r=L; //r为表尾指针
for(int i=0;i<n;i++){
scanf("%d",&x);
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; // r 指向新的表尾节点
}
r->next=NULL; //千万不要忘了，最后把尾指针指向NULL
return L;
}
/* 将单链表按升序重排 */
LNode* InSort(LNode *L){
LNode *p = L->next;
LNode *pre = NULL;
LNode *r = p->next; //r保持p的后继节点指针，以保证不断链
p->next = NULL; //构造只含一个数据的有序表
p = r;
while(p!=NULL){
r = p->next; //保持p的后继节点指针
pre = L;
while(pre->next!=NULL && pre->next->data < p->data){
pre = pre->next; //在有序表中查找插入 *p 的前驱节点 *pre
}
p->next = pre->next; //将 *p 头插法插入 *pre之后
pre->next = p;
p = r; //扫描原单链表中剩下的结点
}
return L;
}
/* 打印单链表 */
void Print(LNode *L){
LNode *p = L->next;
while(p->next != NULL){
printf("%d ",p->data);
p = p->next;
}
printf("%d",p->data);
}
int main(){
int n;
LNode *L=NULL;
while(scanf("%d",&n) != EOF){
L = CreateList(L,n);
L = InSort(L);
Print(L);
printf("\n");
}
return 0;
}
发表于 2017-02-28 16:47:43
回复(0)
#include <iostream>
#include <cstdlib>
//#include<algorithm>
using namespace std;
struct LNode {
int data;
struct LNode *next;
};
typedef struct LNode LNode;
void addlink(LNode *c, int num);
int main() {
int n;
cin >> n;//输入数字数量
int num;
//LNode *a = (LNode*)malloc(sizeof(LNode));
//建立链表根，头节点
LNode* a = new LNode;
//链表赋值
a->data = NULL;
a->next = NULL;
//遍历链表的指针
for (int i = 0; i < n; i++) {
cin >> num;
addlink(a, num);
}
//遍历输出
LNode *p;
p = a;
while (p->next != NULL) {
cout << p->next->data << " ";
p = p->next;
}
return 0;
}
void addlink(LNode *c, int num) {
//首次进入加入链表
//新建一个节点，赋值，设置next
LNode *node = (LNode*)malloc(sizeof(LNode));
node->data = num;
node->next = NULL;
//如果原链表节点为尾（为头节点
//把节点加入链表
//返回
if (c->next == NULL) {
c->next = node;
return;
}
//每次加入新数据
else
{
//新建一个节点储存子节点（从第一个数字开始
LNode *pne = c->next;
//新建一个节点储存父节点（实际上是头节点
LNode *pre = c;
//一次比较链表中的元素
//当节点大于当前节点，则比较后一区间
while (pne != NULL&&pne->data < node->data) {
//如果下区间存在，移动至下一区间
if (pne->next == NULL)//置空和不赋值有区别
{
pne->next = node;
return;
}
//如果不存在下一区间，下一节点为尾节点，则把节点放入链尾
pre = pne;
pne = pne->next;
}
//不满足则放入区间之间
pre->next = node;
node->next = pne;
return;
}
}
#include <cstdlib>
//#include<algorithm>
using namespace std;
struct LNode {
int data;
struct LNode *next;
};
typedef struct LNode LNode;
void addlink(LNode *c, int num);
int main() {
int n;
cin >> n;//输入数字数量
int num;
//LNode *a = (LNode*)malloc(sizeof(LNode));
//建立链表根，头节点
LNode* a = new LNode;
//链表赋值
a->data = NULL;
a->next = NULL;
//遍历链表的指针
for (int i = 0; i < n; i++) {
cin >> num;
addlink(a, num);
}
//遍历输出
LNode *p;
p = a;
while (p->next != NULL) {
cout << p->next->data << " ";
p = p->next;
}
return 0;
}
void addlink(LNode *c, int num) {
//首次进入加入链表
//新建一个节点，赋值，设置next
LNode *node = (LNode*)malloc(sizeof(LNode));
node->data = num;
node->next = NULL;
//如果原链表节点为尾（为头节点
//把节点加入链表
//返回
if (c->next == NULL) {
c->next = node;
return;
}
//每次加入新数据
else
{
//新建一个节点储存子节点（从第一个数字开始
LNode *pne = c->next;
//新建一个节点储存父节点（实际上是头节点
LNode *pre = c;
//一次比较链表中的元素
//当节点大于当前节点，则比较后一区间
while (pne != NULL&&pne->data < node->data) {
//如果下区间存在，移动至下一区间
if (pne->next == NULL)//置空和不赋值有区别
{
pne->next = node;
return;
}
//如果不存在下一区间，下一节点为尾节点，则把节点放入链尾
pre = pne;
pne = pne->next;
}
//不满足则放入区间之间
pre->next = node;
node->next = pne;
return;
}
}
发表于 2020-01-20 10:01:37
回复(0)
你看这代码漂不漂亮
#include<iostream>
using namespace std;
typedef struct LinkNode
{
int data;
struct LinkNode *next = NULL;
}*LinkList;
void insert(LinkList P, int data)
{
while (P->next && P->next->data<data)
P = P->next;
LinkList T = new LinkNode;
T->data = data;
T->next = P->next;
P->next = T;
}
int main()
{
int n, data;
LinkList List = new LinkNode;
cin >> n;
for (int i = 0; i < n && cin >> data; ++i)
insert(List, data);
LinkList P = List->next;
do cout << P->data << ' ';
while(P = P->next);
}
发表于 2020-04-12 14:09:12
回复(1)
#include <iostream>
using namespace std;
struct LinkNode {
int val;
LinkNode *next;
LinkNode(int val, LinkNode* next): val(val), next(next) {}
};
int main() {
int n; cin >> n;
LinkNode* dummy = new LinkNode(-1, nullptr);
for (int i = 0; i < n; i++) {
int x; cin >> x;
LinkNode* pre = dummy;
while (pre->next && pre->next->val < x) {
pre = pre->next;
}
pre->next = new LinkNode(x, pre->next);
}
while (dummy->next) {
cout << dummy->next->val << " ";
dummy = dummy->next;
}
}
挑战最简洁代码，感觉写链表题目的时候，最直接的写法就是最好的写法。
发表于 2024-09-08 17:21:57
回复(0)
#include <cstddef>
#include <iostream>
using namespace std;
struct Node { //链表结点
int data; //数据域
Node* next{}; //指针链域
Node(int data): data(data) {} //构造函数
};
//向链表中插入结点，head为头指针，x为待插入数据
void insert(Node*& head, int x) {
if (head == nullptr || x <= head->data) {
Node* newHead = new Node(x);
newHead->next = head;
head = newHead;
} else {
for (Node* p = head; p; p = p->next) {
if (x > p->data && (p->next == nullptr || x <= p->next->data)) {
Node* node = new Node(x);
node->next = p->next;
p->next = node;
return;
}
}
}
}
int main() {
int n;
while (cin >> n) {
Node* list = nullptr;
while (n--) {
int data;
cin >> data;
insert(list, data);
}
for (Node* p = list; p; p = p->next) {
cout << p->data;
p->next == nullptr ? cout << endl : cout << " ";
}
}
return 0;
}
编辑于 2024-03-11 12:02:01
回复(0)
#include <stdio.h>
#include <stdlib.h>
typedef struct linknode{
struct linknode * next;
int value;
}linknode,*linklist;
int main() {
int n=0;
scanf("%d",&n);
int a[n];
linklist l=(linklist)malloc(sizeof(linknode));
linknode *t=l;
linknode* t1=l;
t->value=-1;
for(int i=0;i<n;i++){
int temp;
scanf("%d ",&temp);
linknode *ln=(linklist)malloc(sizeof(linknode));
ln->value=temp;
while(t->value<temp&&t!=NULL){
t1=t;
t=t->next;
}
if(t==NULL){
t1->next=ln;
ln->next=NULL;
t=l;t1=l;
}else {
t1->next=ln;
ln->next=t;
t=l;t1=l;
}
}
t=t->next;
while(t!=NULL){
printf("%d ",t->value);
t=t->next;
}
return 0;
}
编辑于 2024-03-02 23:08:59
回复(0)
#include <iostream>
#include <vector>
using namespace std;
class LinkNode {
public:
int val;
LinkNode* next;
LinkNode(int data) : val(data), next(NULL) {}
LinkNode() {}
};
int main() {
int n;
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++) {
int cur = 0;
cin >> cur;
v.push_back(cur);
}
for (int i = 0; i < v.size(); i++) {
for (int j = v.size() - 1; j > i; j--) {
if (v[j] < v[j - 1]) {
int temp = v[j];
v[j] = v[j - 1];
v[j - 1] = temp;
}
}
}
LinkNode* head = new LinkNode;
LinkNode* p = head;
for (int i = 0; i < v.size(); i++) {
LinkNode* cur = new LinkNode(v[i]);
p->next = cur;
p = cur;
}
while (head->next != NULL) {
cout << head->next->val << " ";
head = head->next;
}
}
// 64 位输出请用 printf("%lld")
编辑于 2024-01-30 10:40:32
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
