看流星社区

 找回密码
 注册账号
查看: 1822|回复: 0

[算法练习]逆置链表,链表排序,删除节点

[复制链接]

该用户从未签到

发表于 2017-6-1 13:32:28 | 显示全部楼层 |阅读模式
逆置:
使用递归
  1. //考虑递归算法,若只有一个结点,则直接返回,若存在两个结点(a1,a2)则需要做的操作有:      
  2. //a2->next=a1;a1->next=NULL;return a2;
  3. //a2即新的头结点,若有三个结点,则应先将子链(a2,a3)先逆置且返回该子链的新的头结点,然后把子链(a2,a3)当作一个复合结点a2',
  4. //组成新的二元组(a1,a2')然后就可以执行前面相同的操作:a2'->next=a1;a1->next=NULL;return a3';即可,多个以上的结点可同理得到
  5. void ReverseList_Dg(NODE* pCur,NODE** ListHead)  
  6. {  
  7.         if( (NULL == pCur) || (NULL == pCur->next) )  
  8.     {  
  9.         *ListHead = pCur;  
  10.     }  
  11.     else  
  12.     {  
  13.         NODE* pNext = pCur->next;  
  14.         ReverseList_Dg(pNext,ListHead); //返回后续节点的新头节点
  15.         pNext->next = pCur;            //将后继结点指向当前结点。  
  16.         pCur->next = NULL;  
  17.     }  
  18. }  
复制代码
普通的:
  1. //最好画图理解下
  2. void ReverseList_MF(NODE **head)
  3. {
  4.         printf("Begin to Reverse the List From MallocFree\n");
  5.         if(head == NULL ||(*head)->next == NULL || *head == NULL)
  6.         {
  7.                 printf("This list num <= 2\n");
  8.                 return;
  9.         }
  10.         NODE* pPre = *head;    //先前指针  
  11.     NODE* pCur = pPre->next;  //当前指针  
  12.     NODE* pNext = NULL;       //后继指针  
  13.     while(pCur!=NULL)  
  14.     {  
  15.         pNext = pCur->next;  
  16.         pCur->next = pPre;  //把当前指向前面那个,这个时候就实现了逆向了.
  17.         pPre = pCur;  
  18.         pCur = pNext;  
  19.     }  
  20.         (*head)->next = NULL;  
  21.         *head = pPre;        //记录下新的头结点  
  22. }
复制代码
上个图:图片有点大...




第二张:




还有一种:跟上面差不多
  1. void ReverseList_New(NODE** pHead)
  2. {
  3.         printf("Begin to Reverse the List New \n");
  4.         if (pHead == NULL || (*pHead)->next == NULL)
  5.     {
  6.         return;
  7.     }
  8.     NODE* pRev = NULL;
  9.     NODE* pCur = *pHead;
  10.     while(pCur != NULL)
  11.     {
  12.         NODE* pTemp = pCur;   
  13.         pCur = pCur->next;      
  14.         pTemp->next = pRev;      
  15.         pRev = pTemp;
  16.     }
  17.        
  18.         //return pRev;//返回新的头节点
  19.         (*pHead)->next = NULL;
  20.         *pHead = pRev;
  21. }
复制代码
删除:
原文见:
http://www.cnblogs.com/bakari/p/4013812.html

用O(1)的时间复杂度删除单链表中的某个节点

这是一道广为流传的Google面试题,考察我们对链表的操作和时间复杂度的了解,咋一看这道题还想不出什么较好的解法,但人家把题出在这,肯定是有解法的。一般单链表删除某个节点,需要知道删除节点的前一个节点,则需要O(n)的遍历时间,显然常规思路是不行的。在仔细看题目,换一种思路,既然不能在O(1)得到删除节点的前一个元素,但我们可以轻松得到后一个元素,这样,我们何不把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素。可见,该方法可行,但如果待删除节点为最后一个节点,则不能按照以上思路,没有办法,只能按照常规方法遍历,时间复杂度为O(n),是不是不符合题目要求呢?可能很多人在这就会怀疑自己的思考,从而放弃这种思路,最后可能放弃这道题,这就是这道面试题有意思的地方,虽看简单,但是考察了大家的分析判断能力,是否拥有强大的心理,充分自信。其实我们分析一下,仍然是满足题目要求的,如果删除节点为前面的n-1个节点,则时间复杂度为O(1),只有删除节点为最后一个时,时间复杂度才为O(n),所以平均的时间复杂度为:(O(1)
* (n-1) + O(n))/n = O(1);仍然为O(1).下面见代码:
  1. void List_DeleteNode_Google(NODE *pListHead, NODE *pToBeDeleted)
  2. {
  3.      if (!pListHead || !pToBeDeleted)
  4.          return;
  5.    
  6.          if (pToBeDeleted->data != NULL) {
  7.                  NODE *pNext = pToBeDeleted->next;
  8.                  pToBeDeleted->next = pNext->next;
  9.                  pToBeDeleted->data = pNext->data;
  10.         delete pNext;
  11.         pNext = NULL;
  12.      }
  13.      else { //待删除节点为尾节点
  14.          NODE *pTemp = pListHead;
  15.                  while(pTemp->next != pToBeDeleted)
  16.                          pTemp = pTemp->next;
  17.                  pTemp->next = NULL;
  18.         delete pToBeDeleted;
  19.         pToBeDeleted = NULL;
  20.     }
  21.          pListHead->ListLen--;
  22. }
复制代码




排序
我使用了选择排序
  1. /********************************* 链表的排序  *******************************************/  
  2. /*
  3. ==========================
  4. 功能:选择排序(由小到大)
  5. 返回:指向链表表头的指针
  6. ==========================
  7. 选择排序的基本思想就是反复从还未排好序的那些节点中,
  8. 选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,
  9. 依次重新组合成一个链表。
  10. 我认为写链表这类程序,关键是理解:
  11. head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;
  12. 任 意一个节点p的地址,只能通过它前一个节点的next来求得。
  13. 单向链表的选择排序图示:
  14. ---->[1]---->[3]---->[2]...----> [n]---->[NULL](原链表)
  15. head   1->next  3->next  2->next   n->next
  16. ---->[NULL](空链表)
  17. first
  18. tail
  19. ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
  20. first   1->next  2->next  3->next   tail->next
  21. 1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;
  22. 2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);
  23. 3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;
  24. */  
  25. NODE* SelectSort(PNODE *head)  
  26. {  
  27.         if(head == NULL || *head == NULL || (*head)->next == NULL)
  28.                 return NULL;
  29.     NODE *pfirst;      /* 排列后有序链的表头指针 */  
  30.     NODE *ptail;       /* 排列后有序链的表尾指针 */  
  31.     NODE *pminBefore;  /* 保留键值更小的节点的前驱节点的指针 */  
  32.     NODE *pmin;        /* 存储最小节点   */  
  33.     NODE *p;           /* 当前比较的节点 */  
  34.    
  35.     pfirst = NULL;  
  36.     while (*head != NULL)         /*在链表中找键值最小的节点。*/  
  37.     {  
  38.     /* 注意:这里for语句就是体现选择排序思想的地方 */  
  39.         for (p = *head, pmin = *head; p->next != NULL; p = p->next) /*循环遍历链表中的节点,找出此时最小的节点。*/  
  40.         {  
  41.             if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/  
  42.             {  
  43.                 pminBefore = p;           /*保存找到节点的前驱节点:显然p->next的前驱节点是p。*/  
  44.                 pmin       = p->next;     /*保存键值更小的节点。*/  
  45.             }  
  46.         }  
  47.    
  48.     /*上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表。*/  
  49.       
  50.         /*第一件事*/  
  51.         if (pfirst == NULL)     /* 如果有序链表目前还是一个空链表                      */  
  52.         {  
  53.             pfirst = pmin;      /* 第一次找到键值最小的节点。                          */  
  54.             ptail  = pmin;      /* 注意:尾指针让它指向最后的一个节点。                */  
  55.         }  
  56.         else                    /* 有序链表中已经有节点                                */  
  57.         {  
  58.             ptail->next = pmin; /* 把刚找到的最小节点放到最后,即让尾指针的next指向它。*/  
  59.             ptail = pmin;       /* 尾指针也要指向它。                                  */  
  60.         }  
  61.   
  62.         /*第二件事*/  
  63.         if (pmin == *head)        /* 如果找到的最小节点就是第一个节点                    */  
  64.         {  
  65.             *head = (*head)->next;   /* 显然让head指向原head->next,即第二个节点,就OK       */  
  66.         }  
  67.         else /*如果不是第一个节点*/  
  68.         {  
  69.             pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/  
  70.         }  
  71.     }  
  72.   
  73.     if (pfirst != NULL)     /*循环结束得到有序链表first                */  
  74.     {  
  75.         ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */   
  76.     }  
  77.     *head = pfirst;  
  78.     return *head;  
  79. }  
复制代码

全部代码:
  1. #include <stdio.h>
  2. const int N=6;  
  3. typedef struct _node{ //单链表  
  4.       int data;  
  5.           int ListLen;
  6.       struct _node* next;  
  7. }NODE,*PNODE;  
  8. //由数组创建单链表
  9. PNODE CreateList(int a[N])  
  10. {  
  11.         printf("Begin to Create the List\n");
  12.     NODE* ListHead=new NODE();  
  13.     ListHead->data=a[0];  
  14.     ListHead->next=NULL;  
  15.     for(int i=N-1;i>=1;i--)  
  16.     {  
  17.         NODE* p=new NODE();  
  18.         p->data=a[i];  
  19.                 p->ListLen = N;
  20.         p->next=ListHead->next;  
  21.         ListHead->next=p;  
  22.     }  
  23.         //ListHead->ListLen = N;
  24.     return ListHead;  
  25. }  
  26. ///输出单链表
  27. void PrintList(PNODE ListHead)  
  28. {  
  29.     if(NULL==ListHead)
  30.         {
  31.                 printf("The List is empty!");
  32.                 return;
  33.         }
  34.     else  
  35.     {  
  36.         NODE* p=ListHead;  
  37.         while(p!=NULL)  
  38.         {  
  39.                         printf("%d ",p->data);
  40.             p=p->next;  
  41.         }  
  42.     }  
  43.         printf("\n\n");
  44. }  
  45. void ReverseList_New(NODE** pHead)
  46. {
  47.         printf("Begin to Reverse the List New \n");
  48.         if (pHead == NULL || (*pHead)->next == NULL)
  49.     {
  50.         return;
  51.     }
  52.     NODE* pRev = NULL;
  53.     NODE* pCur = *pHead;
  54.     while(pCur != NULL)
  55.     {
  56.         NODE* pTemp = pCur;   
  57.         pCur = pCur->next;      
  58.         pTemp->next = pRev;      
  59.         pRev = pTemp;
  60.     }
  61.        
  62.         //return pRev;//返回新的头节点
  63.         (*pHead)->next = NULL;
  64.         *pHead = pRev;
  65. }
  66. //考虑递归算法,若只有一个结点,则直接返回,若存在两个结点(a1,a2)则需要做的操作有:      
  67. //a2->next=a1;a1->next=NULL;return a2;
  68. //a2即新的头结点,若有三个结点,则应先将子链(a2,a3)先逆置且返回该子链的新的头结点,然后把子链(a2,a3)当作一个复合结点a2',
  69. //组成新的二元组(a1,a2')然后就可以执行前面相同的操作:a2'->next=a1;a1->next=NULL;return a3';即可,多个以上的结点可同理得到
  70. void ReverseList_Dg(NODE* pCur,NODE** ListHead)  
  71. {  
  72.         if( (NULL == pCur) || (NULL == pCur->next) )  
  73.     {  
  74.         *ListHead = pCur;  
  75.     }  
  76.     else  
  77.     {  
  78.         NODE* pNext = pCur->next;  
  79.         ReverseList_Dg(pNext,ListHead); //返回后续节点的新头节点
  80.         pNext->next = pCur;            //将后继结点指向当前结点。  
  81.         pCur->next = NULL;  
  82.     }  
  83. }  
  84. //最好画图理解下
  85. void ReverseList_MF(NODE **head)
  86. {
  87.         printf("Begin to Reverse the List From MallocFree\n");
  88.         if(head == NULL ||(*head)->next == NULL || *head == NULL)
  89.         {
  90.                 printf("This list num <= 2\n");
  91.                 return;
  92.         }
  93.         NODE* pPre = *head;    //先前指针  
  94.     NODE* pCur = pPre->next;  //当前指针  
  95.     NODE* pNext = NULL;       //后继指针  
  96.     while(pCur!=NULL)  
  97.     {  
  98.         pNext = pCur->next;  
  99.         pCur->next = pPre;  //把当前指向前面那个,这个时候就实现了逆向了.
  100.         pPre = pCur;  
  101.         pCur = pNext;  
  102.     }  
  103.         (*head)->next = NULL;  
  104.         *head = pPre;        //记录下新的头结点  
  105. }
  106. void List_DeleNode(PNODE* list,int pos)
  107. {
  108.         if( (list != NULL) && (0 <= pos) && (pos < (*list)->ListLen) )//&& ((*list)->next != NULL) )
  109.         {
  110.                 if((*list)->next == NULL)
  111.                 {
  112.                         return;
  113.                 }
  114.                 NODE* p = *list;
  115.                 NODE *pb = NULL;
  116.                 for (int i = 0; i <= pos-1; i++) //让p指向第pos个节点,pb指向第n-1个节点
  117.                 {
  118.                         pb = p;
  119.                         p = p->next;
  120.                 }
  121.                 pb->next = p->next;//让要删除的节点的上一个节点的指针指向要删除节点的后一个节点
  122.                 //减少一个节点
  123.                 (*list)->ListLen--;
  124.                 delete[] p;
  125.         }
  126.         return;
  127. }
  128. PNODE list_GetNode(PNODE* list,int pos)
  129. {
  130.         if( (list != NULL) && (0 <= pos) && (pos < (*list)->ListLen) )
  131.         {
  132.                 NODE *p = *list;
  133.                 for (int i = 0; i < pos-1; i++)
  134.                 {
  135.                         p = p->next;
  136.                 }
  137.                 return p;
  138.         }
  139.         return NULL;
  140.        
  141. }
  142. /*
  143. 一般单链表删除某个节点,需要知道删除节点的前一个节点,则需要O(n)的遍历时间,
  144. 显然常规思路是不行的。在仔细看题目,换一种思路,既然不能在O(1)得到删除节点的前一个元素,
  145. 但我们可以轻松得到后一个元素,这样,我们何不把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素。
  146. 可见,该方法可行,但如果待删除节点为最后一个节点,则不能按照以上思路,没有办法,只能按照常规方法遍历,时间复杂度为O(n)
  147. */
  148. void List_DeleteNode_Google(NODE *pListHead, NODE *pToBeDeleted)
  149. {
  150.      if (!pListHead || !pToBeDeleted)
  151.          return;
  152.    
  153.          if (pToBeDeleted->data != NULL) {
  154.                  NODE *pNext = pToBeDeleted->next;
  155.                  pToBeDeleted->next = pNext->next;
  156.                  pToBeDeleted->data = pNext->data;
  157.         delete pNext;
  158.         pNext = NULL;
  159.      }
  160.      else { //待删除节点为尾节点
  161.          NODE *pTemp = pListHead;
  162.                  while(pTemp->next != pToBeDeleted)
  163.                          pTemp = pTemp->next;
  164.                  pTemp->next = NULL;
  165.         delete pToBeDeleted;
  166.         pToBeDeleted = NULL;
  167.     }
  168.          pListHead->ListLen--;
  169. }
  170. /********************************* 链表的排序  *******************************************/  
  171. /*
  172. ==========================
  173. 功能:选择排序(由小到大)
  174. 返回:指向链表表头的指针
  175. ==========================
  176. 选择排序的基本思想就是反复从还未排好序的那些节点中,
  177. 选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,
  178. 依次重新组合成一个链表。
  179. 我认为写链表这类程序,关键是理解:
  180. head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;
  181. 任 意一个节点p的地址,只能通过它前一个节点的next来求得。
  182. 单向链表的选择排序图示:
  183. ---->[1]---->[3]---->[2]...----> [n]---->[NULL](原链表)
  184. head   1->next  3->next  2->next   n->next
  185. ---->[NULL](空链表)
  186. first
  187. tail
  188. ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
  189. first   1->next  2->next  3->next   tail->next
  190. 1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;
  191. 2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);
  192. 3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;
  193. */  
  194. NODE* SelectSort(PNODE *head)  
  195. {  
  196.         if(head == NULL || *head == NULL || (*head)->next == NULL)
  197.                 return NULL;
  198.     NODE *pfirst;      /* 排列后有序链的表头指针 */  
  199.     NODE *ptail;       /* 排列后有序链的表尾指针 */  
  200.     NODE *pminBefore;  /* 保留键值更小的节点的前驱节点的指针 */  
  201.     NODE *pmin;        /* 存储最小节点   */  
  202.     NODE *p;           /* 当前比较的节点 */  
  203.    
  204.     pfirst = NULL;  
  205.     while (*head != NULL)         /*在链表中找键值最小的节点。*/  
  206.     {  
  207.     /* 注意:这里for语句就是体现选择排序思想的地方 */  
  208.         for (p = *head, pmin = *head; p->next != NULL; p = p->next) /*循环遍历链表中的节点,找出此时最小的节点。*/  
  209.         {  
  210.             if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/  
  211.             {  
  212.                 pminBefore = p;           /*保存找到节点的前驱节点:显然p->next的前驱节点是p。*/  
  213.                 pmin       = p->next;     /*保存键值更小的节点。*/  
  214.             }  
  215.         }  
  216.    
  217.     /*上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表。*/  
  218.       
  219.         /*第一件事*/  
  220.         if (pfirst == NULL)     /* 如果有序链表目前还是一个空链表                      */  
  221.         {  
  222.             pfirst = pmin;      /* 第一次找到键值最小的节点。                          */  
  223.             ptail  = pmin;      /* 注意:尾指针让它指向最后的一个节点。                */  
  224.         }  
  225.         else                    /* 有序链表中已经有节点                                */  
  226.         {  
  227.             ptail->next = pmin; /* 把刚找到的最小节点放到最后,即让尾指针的next指向它。*/  
  228.             ptail = pmin;       /* 尾指针也要指向它。                                  */  
  229.         }  
  230.   
  231.         /*第二件事*/  
  232.         if (pmin == *head)        /* 如果找到的最小节点就是第一个节点                    */  
  233.         {  
  234.             *head = (*head)->next;   /* 显然让head指向原head->next,即第二个节点,就OK       */  
  235.         }  
  236.         else /*如果不是第一个节点*/  
  237.         {  
  238.             pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/  
  239.         }  
  240.     }  
  241.   
  242.     if (pfirst != NULL)     /*循环结束得到有序链表first                */  
  243.     {  
  244.         ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */   
  245.     }  
  246.     *head = pfirst;  
  247.     return *head;  
  248. }  
  249. int main()  
  250. {  
  251.     int a[N] = {5,7,2,4,10,1};  
  252.     NODE* list = CreateList(a);  
  253.     PrintList(list);  
  254.         //递归方法
  255.     NODE* pTemp = list;  
  256.         printf("Begin to Reverse the List From Recursion \n");
  257.     ReverseList_Dg(pTemp,&list);  
  258.         PrintList(list);  
  259.         //普通方法
  260.         ReverseList_MF(&list);
  261.         PrintList(list);
  262.         //普通方法2
  263.         ReverseList_New(&list);
  264.         PrintList(list);
  265.         //删除节点
  266.         printf("Delete second nodes\n");
  267.         List_DeleNode(&list,1);
  268.         PrintList(list);
  269.         //删除节点
  270.         printf("Del Node From Google -- Delete second nodes\n");
  271.         List_DeleteNode_Google(list,list_GetNode(&list,2));
  272.         PrintList(list);
  273.        
  274.         //选择排序
  275.         printf("SelectSort\n");
  276.         SelectSort(&list);
  277.         PrintList(list);
  278.        
  279.     getchar();
  280. }  
复制代码
点击按钮快速添加回复内容: 支持 高兴 激动 给力 加油 苦寻 生气 回帖 路过 感恩
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

小黑屋|手机版|Archiver|看流星社区 |网站地图

GMT+8, 2024-3-19 15:00

Powered by Kanliuxing X3.4

© 2010-2019 kanliuxing.com

快速回复 返回顶部 返回列表