无头链表创建
#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;
}
