算法练习-简单链表

无头链表创建

#include <stdio.h>
#include <stdlib.h>

typedef struct node //链表
{
	 int val; //数据域
	 struct node *next; //指针域
} Node;

Node *creatTail(Node **head) //尾插法创建链表
{
	 int val;
	 Node *p = *head;
	Node *q = NULL;
	while (1)
	 {
		 scanf("%d", &val);
		if (val == -1)
		 {
			break;
		}
		 q = (Node *)malloc(sizeof(Node));
		 q->val = val;
		if (*head == NULL)
		 {
		 *head = q;
			 p = q;
	 }
	 else
	 {
	 p->next = q;
	 p = p->next;
	}
	 }
	 p->next = NULL;
}

Node* resetlist(Node* head) {
    Node* p = head, *q = NULL;
    while (p != NULL) {
        Node* t = p->next;
        p->next = q;
        q = p;
        p = t;
    }
    return q;
}

void printList(Node *head) //链表遍历
{
	Node *p = head;
	 while (p)
	 {
		printf("%d", p->val);
		 p = p->next;
	 }
}

int main()
{
	Node *head = NULL; //链表
	creatTail(&head); //头插法创建链表
	printList(resetlist(head));  //链表的表达
	return 0;
}

链表逆置

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int date;
    struct node* next;
}Node;
Node* creatlist(Node **head){
	Node* p=*head;
	int n;
	Node* q=NULL;
	while(1){
		scanf("%d",&n);
		if(n==-1){
			break;
		}
		q=(Node*)malloc(sizeof(Node));
		q->date=n;
		if(*head==NULL){
			*head=q;
			p=q;
		}
		else{
			p->next=q;
			p=p->next;
		}
	}
	p->next=NULL;
	
}

Node* resetlist(Node* head) {//三指针原地逆置
    Node* p = head, *q = NULL;
    while (p != NULL) {
        Node* t = p->next;
        p->next = q;
        q = p;
        p = t;
    }
    return q;
}
void outPut(Node* head) {
    Node* p = head;
    while (p!= NULL) 
    {
        printf("%2d", p->date);
        p = p->next;
    }
}

int main() {
	Node* head=NULL;
    creatlist(&head);
    outPut(resetlist(head));
    return 0;
}

合并两个有序链表(无头）

要注意空链表的合并

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int date;
    struct node* next;
}Node;
Node* creatlist(Node **head){//注意链表创建
	Node* p=*head;
	int  n;
	Node* q=NULL;
	scanf("%d",&n);
	if(n==0){
		return NULL;//如果输入0直接返回NULL
	}
	else{
		q=(Node*)malloc(sizeof(Node));//如果非0，将第一个数和后面连起来
		q->date=n;
		if(*head==NULL){
			*head=q;
			p=q;
		}
		else{
			p->next=q;
			p=p->next;
		}
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		q=(Node*)malloc(sizeof(Node));
		q->date=n;
		if(*head==NULL){
			*head=q;
			p=q;
		}
		else{
			p->next=q;
			p=p->next;
		}
	}
	p->next=NULL;
	
	}
	
}

Node* conlist(Node* node1,Node* node2){
	if(node1==NULL){//判断是否为空，如果一个为空，输出另一个，都为空则输出NULL
		return node2;
	}
	else if(node2==NULL){
		return node1;
	}
	else if(node1==NULL&&node2==NULL){
		return NULL;
	}
	else{
	Node* newhead;
	Node* p;
	Node* q;
	newhead=node1->date>node2->date?node2:node1;
	if(newhead==node1){
		
	p =node1->next;
	q=node2;
	}
	else{
		
	p=node1;
	q=node2->next;
	}
	Node* temp=newhead;
	while(p||q){
		if(p&&q==NULL){
			temp->next=p;
			p=p->next;
		}
		else if(q&&p==NULL){
			temp->next=q;
			q=q->next;
		}
		else if(p->date>q->date){
			temp->next=q;
			q=q->next;
		}
		else{
			temp->next=p;
			p=p->next;
		}
			temp=temp->next;
	}
	return newhead;
	}
}

void outPut(Node* head) {
    Node* p = head;
    while (p!= NULL) 
    {
        printf("%2d", p->date);
        p = p->next;
    }
}

int main() {
	Node* head1=NULL;
	Node* head2=NULL;
    creatlist(&head1);
    creatlist(&head2);
    outPut(conlist(head1,head2));
    return 0;
}

删除链表的倒数第N个结点(无头）

方法：快慢指针

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int date;
    struct node* next;
}Node;

Node* creatlist(Node **head){
	Node* p=*head;
	int n;
	Node* q=NULL;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		q=(Node*)malloc(sizeof(Node));
		q->date=n;
		if(*head==NULL){
			*head=q;
			p=q;
		}
		else{
			p->next=q;
			p=p->next;
		}
	}
	p->next=NULL;
	
}

void clist(Node* head,int n){
	Node* q=head;
	Node* p=head;
	for(int x=0;x!=n;x++){//快指针向后指，结果是离慢指针距离为n
		p=p->next;
	}
	while(p->next){//两个指针一起移动，移速一样，到p->next为空，找到要删除节点的位置
		p=p->next;
		q=q->next;
	}
	q->next=q->next->next;//删除
}

void outPut(Node* head) {
    Node* p = head;
    while (p!= NULL) 
    {
        printf("%6d", p->date);
        p = p->next;
    }
}

int main() {
	Node* head=NULL;
	creatlist(&head);
	clist(head,3);
	outPut(head);
    return 0;
}

两两交换链表中的结点(无头）

struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode dummyHead;
    dummyHead.next = head;
    struct ListNode* temp = &dummyHead;
    while (temp->next != NULL && temp->next->next != NULL) {
        struct ListNode* node1 = temp->next;
        struct ListNode* node2 = temp->next->next;
        temp->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        temp = node1;
    }
    return dummyHead.next;
}