对一个单链表进行逆序排列。

冷不防 2022-05-13 11:22 169阅读 0赞

算法:当建立好一个链表后，指针的方向是固定的，从某种意义上来说只能从head开始，每一个next都是指向下一个，即从左到右，如果要逆序排列，首先很容易想到要访问到尾节点，将其当做新的头结点，然后让它去指向倒数第二个倒数第三个等等。可问题来了，找到新的头结点到时很容易，那如果让它按照倒数第二个，倒数第三个......也就是从右至左的逆序访问呢？毕竟链表里没有哪个指针可以指向反方向的啊，研究了一下午的老谭的算法，终于想通了（在这里小小的膜拜下，确实牛逼！）。逆序的核心算法如下：首先去遍历初始链表，这个比较简单p2=p1;p1=p1->next;(其中p1主要访问下一结点，p2记录p1走过的地方),访问到最后我们就可以找到新的头结点(即这里的尾节点)，然后赋值新的指针,newp=newhead=p1;接下来就是算法的经典步骤了，此时p1，newp，newhead都指向最后一个节点，而p2指向倒数第二个节点，立刻使p2->next=null；这样就等于丢掉了最后一个节点，使得p2指向了新的链表的尾节点（此时链表少了一个节点）。这是第一趟的步骤，为了找出规律，继续看第二趟，也就是说继续让p1，p2指向head(head是原链表的头结点，它一直都没有动，以方便每趟的初始化)，然后去遍历链表节点，这时又可以找到最后一个节点(原链表的倒数第二个节点)，然后又断开它，这时，已经断开了两个节点了，第一趟找到的是新的头结点，那么立刻连接这个第二次丢掉的节点，重新组建新链表，即newp->next=p1,这样这两个节点就连接起来了，可是这样还不够，为了遍历新的链表，得有一个指针啊，还得让newp指针过去，它现在还在新的头结点哪里呢（不用不是浪费了），让它去倒数第二个节点的地方（以方便以后的连接），结合起来就是newp=newp->next=p1;依次这样循环len次即可(len为链表节点数)。代码如下:

#include <stdio.h>
    #include <malloc.h>
    struct stu
    {
    	int num;
    	struct stu *next;
    };
    void main()
    { int i;//用以遍历循环
      int len;//链表长度
      struct stu *p1,*p2,*head,*newhead,*newp;
      p1=p2=head=(struct stu*)malloc(sizeof(struct stu));
      printf("--------输入链表开始----------\n");
      printf("输入一个节点(输入0则退出):\n");
      scanf("%3d",&p1->num);
      len=1;//长度加1
      while(p1->num!=0)
      {
    	  p1=(struct stu*)malloc(sizeof(struct stu));//p1指向新节点
    	  printf("继续输入节点(输入0则退出):\n");
    	  scanf("%3d",&p1->num);
    	  if (p1->num==0)
    	    p2->next=NULL;//只有一个节点
    	  else
    	  {
            p2->next=p1;
    	    p2=p1;
    	    len++;}
      }
      printf("---------输出原始链表----------\n");
      p1=head;//初始化指针用以输出
      for (i=1;i<=len;i++)
      {
    	  printf("%3d ",p1->num);
    	  p1=p1->next;
      }
      printf("\n");
      printf("------对原始链表排序并输出------\n");
      for (i=1;i<=len;i++)
      {
        p1=p2=head;
    	while(p1->next!=NULL)//此循环非常重要，去指向每趟尾节点
    	{p2=p1;
    	p1=p1->next;//此时p1指向最后一个，p2为倒数第二个，注意循环条件
    	}
    	if(i==1)//第一趟时,将尾节点作为新的头结点
           newhead=newp=p1;
    	else
    		newp=newp->next=p1;//每趟都新加入一个之前链表丢掉的节点
    	p2->next=NULL;//每趟的倒数第二个节的next都指向空，等于切断了倒数第一个节点
      }
      //输出逆序后的链表
      p1=newhead;
      for (i=1;i<=len;i++)
      {printf("%4d",p1->num);
       p1=p1->next;
      }
      printf("\n");
    }

![1354788569_3222.jpg][]

[1354788569_3222.jpg]: https://img-my.csdn.net/uploads/201212/06/1354788569_3222.jpg