单链表逆序详解

发布时间:2017-1-18 18:01:59 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"单链表逆序详解",主要涉及到单链表逆序详解方面的内容,对于单链表逆序详解感兴趣的同学可以参考一下。

1、具有链表头的单链表 一段单链表逆序的程序  typedefstruct student {     int number;     char name[20];     int score;     struct student *next; }student; student *reverse(student *stu) {     student *p1,*p2,*p3;     if(stu == NULL ||stu->next == NULL)         return stu;     p1=stu->next;                           //p1指向链表头节点的下一个节点     p2=p1->next;     p1->next=NULL;     while(p2)     {         p3=p2->next;         p2->next = p1;         p1=p2;         p2=p3;     }     printf("p1 = %d,next = %d\n",p1->number,p1->next->number);     stu->next=p1;                           //将链表头节点指向p1     return stu; } 分析: 假设需要逆序的单链表为: 则逆序以后的链表为:   过程: (1)取p1指向header->next                     p1=stu->next;          p2保留p1->next                             p2=p1->next;          将p1->next置为NULL,因为单链表逆序以后,当前的p1节点为尾节点                   p1->next=NULL;   (2)取p3保留p2->next                       p3=p2->next;         将p2插入p1之前                            p2->next= p1;          p1指向p2指向的节点      p1=p2;          p2指向p3指向的节点       p2=p3;   循环一次修改以后的单链表如下:   (3)重复步骤(2)   循环一次修改以后的单链表如下:   (4)将header->next指向p1,完成整个单链表的逆序   2、无链表头的单链表 一段单链表逆序的程序  typedefstruct student {     int number;     char name[20];     int score;     struct student *next; }student; student *reverse2(student *stu) {         student *p1,*p2,*p3;         if(stu == NULL ||stu->next== NULL)                 returnstu;         p1=stu;                                   //p1指向链表的第一个节点                                                          p2=p1->next;     p1->next = NULL;         while(p2)         {                 p3=p2->next;                 p2->next= p1;                 p1=p2;                 p2=p3;         }         printf("p1 = %d,next =%d\n ",p1->number,p1->next->number);         stu=p1;                                  //将链表第一个节点指向p1         return stu; }                                           //////////////////////////////////////////////////////////////////////////////// 设链表节点为 [cpp] view plaincopy 1.    typedef struct tagListNode{   2.        int data;   3.        struct tagListNode* next;   4.    }ListNode, *List;   要求将一带链表头List head的单向链表逆序。 分析:   1). 若链表为空或只有一个元素,则直接返回;   2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继;   3). 重复2),直到q为空   4). 调整链表头和链表尾 示例:以逆序A->B->C->D为例,图示如下   实现及测试代码如下: [cpp:nogutter] view plaincopy 1.    #include <stdio.h>   2.    #include <stdlib.h>   3.       4.    typedef struct tagListNode{   5.        int data;   6.        struct tagListNode* next;   7.    }ListNode, *List;   8.       9.    void PrintList(List head);   10.  List ReverseList(List head);   11.     12.  int main()   13.  {   14.      //分配链表头结点   15.      ListNode *head;   16.      head = (ListNode*)malloc(sizeof(ListNode));   17.      head->next = NULL;   18.      head->data = -1;   19.     20.      //将[1,10]加入链表   21.      int i;   22.      ListNode *p, *q;   23.      p = head;   24.      for(int i = 1; i <= 10; i++)   25.      {   26.          q = (ListNode *)malloc(sizeof(ListNode));   27.          q->data = i;   28.          q->next = NULL;   29.          p->next = q;   30.          p = q;           31.      }   32.     33.      PrintList(head);           /*输出原始链表*/   34.      head = ReverseList(head);  /*逆序链表*/   35.      PrintList(head);           /*输出逆序后的链表*/   36.      return 0;   37.  }   38.     39.  List ReverseList(List head)   40.  {   41.      if(head->next == NULL || head->next->next == NULL)     42.      {   43.         return head;   /*链表为空或只有一个元素则直接返回*/   44.      }   45.     46.      ListNode *t = NULL,   47.               *p = head->next,   48.               *q = head->next->next;   49.      while(q != NULL)   50.      {           51.        t = q->next;   52.        q->next = p;   53.        p = q;   54.        q = t;   55.      }   56.     57.      /*此时q指向原始链表最后一个元素,也是逆转后的链表的表头元素*/   58.      head->next->next = NULL;  /*设置链表尾*/   59.      head->next = p;           /*调整链表头*/   60.      return head;   61.  }   62.     63.  void PrintList(List head)   64.  {   65.      ListNode* p = head->next;   66.      while(p != NULL)   67.      {   68.          printf("%d ", p->data);   69.          p = p->next;   70.      }   71.      printf("/n");   72.  }  

上一篇:25个增强iOS应用程序性能的提示和技巧(初级篇)
下一篇:(10) - 枚举 (图)

相关文章

相关评论