单链表的前K个的逆序输出

单链表逆序输出也是常被面试官问到题算法题，所以自己就总结了一下，在此贴出算法，与小伙伴们相互交流。

首先要有三个指针，前两个分别指向首节点，首节点的下一个节点，第三个是临时指针，是为了储存首节点的下一个节点的下一个节点，防止链表断裂

图1

输出函数一共两个参数，第一个是链表本身，第二是K值

首先让new等于头结点的next节点，old为new结点的next节点

为了让逆序输出，必须定义一个计数器count，count初值为1，用于终止循环的条件。

每次循环，必须先指定temp节点为old的next节点(temp=old->next)，再将old的指针指向的节点改为new(old->next=new)，再将new节点向右移动为old原来的位置(new=old)，再将old节点向右移动为temp的位置(old=temp)，并将count++，当count=k时跳出循环

图2

跳出循环时，先将head的next的next（也就是1节点的next）指向old，再将head指向new，不能调换顺序，就完成了逆序

图3

代码如下所示

#include <stdio.h>
#include <malloc.h>
/*链表节点结构*/
typedef struct node{
    int data;
    struct node * pNext;
}NODE,*PNODE;
/*函数声明*/
PNODE create_list();
void show_list(PNODE p);
void show_list_list(PNODE p);
PNODE reversedOrder(PNODE p ,int k);
/*主函数*/
int main(){
    int k;
    int len;
    PNODE pHead=NULL;
    pHead=create_list();
    show_list(pHead);
    len=show_list_length(pHead);
    printf("\n%d\n",len);
    reversedOrder(pHead,2);
    show_list(pHead);
    return 0;
}
/*生产链表*/
PNODE create_list(void){
    int len;
    int val;
    int i;
    scanf("%d\n",&len);
    PNODE pHead=(PNODE)malloc(sizeof(NODE));
    if(pHead==NULL){
        printf("error");
    }
    PNODE pTail=pHead;
    pTail->pNext=NULL;
    for(i=0;i<len;i++){
        scanf("%d",&val);
        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        if(pNew==NULL){
        printf("error");
        }
        pNew->data=val;
        pTail->pNext=pNew;
        pNew->pNext=NULL;
        pTail=pNew;
    }
    return pHead;
}
/*显示链表*/
void show_list(PNODE p){
    PNODE p1=p->pNext;
    if(p1==NULL){
        printf("error");
    }
    while(p1){
        printf("%d",p1->data);
        p1=p1->pNext;
    }
}
/*显示链表长度*/
int show_list_length(PNODE p){
    int count=0;
    PNODE p1=p->pNext;
    if(p1==NULL){
        printf("error");
    }
    while(p1){
        count++;
        p1=p1->pNext;
    }
    return count;
}
/*逆序*/
PNODE reversedOrder(PNODE p,int k){
    int count=1;
    PNODE oNew=p->pNext;
    PNODE old=oNew->pNext;
    while(count<k){
        PNODE temp=old->pNext;
        old->pNext=oNew;
        oNew=old;
        old=temp; 
        count++;
    }
    
    p->pNext->pNext=old;
    p->pNext=oNew;
    //return oNew;
}

测试结果：

图4

这就是我对逆序的理解。

单链表的前K个的逆序输出

推荐阅读