- 注册时间
- 2011-3-6
- 最后登录
- 1970-1-1
该用户从未签到
|
逆置:
使用递归- //考虑递归算法,若只有一个结点,则直接返回,若存在两个结点(a1,a2)则需要做的操作有:
- //a2->next=a1;a1->next=NULL;return a2;
- //a2即新的头结点,若有三个结点,则应先将子链(a2,a3)先逆置且返回该子链的新的头结点,然后把子链(a2,a3)当作一个复合结点a2',
- //组成新的二元组(a1,a2')然后就可以执行前面相同的操作:a2'->next=a1;a1->next=NULL;return a3';即可,多个以上的结点可同理得到
- void ReverseList_Dg(NODE* pCur,NODE** ListHead)
- {
- if( (NULL == pCur) || (NULL == pCur->next) )
- {
- *ListHead = pCur;
- }
- else
- {
- NODE* pNext = pCur->next;
- ReverseList_Dg(pNext,ListHead); //返回后续节点的新头节点
- pNext->next = pCur; //将后继结点指向当前结点。
- pCur->next = NULL;
- }
- }
复制代码 普通的:- //最好画图理解下
- void ReverseList_MF(NODE **head)
- {
- printf("Begin to Reverse the List From MallocFree\n");
- if(head == NULL ||(*head)->next == NULL || *head == NULL)
- {
- printf("This list num <= 2\n");
- return;
- }
- NODE* pPre = *head; //先前指针
- NODE* pCur = pPre->next; //当前指针
- NODE* pNext = NULL; //后继指针
- while(pCur!=NULL)
- {
- pNext = pCur->next;
- pCur->next = pPre; //把当前指向前面那个,这个时候就实现了逆向了.
- pPre = pCur;
- pCur = pNext;
- }
- (*head)->next = NULL;
- *head = pPre; //记录下新的头结点
- }
复制代码 上个图:图片有点大...
第二张:
还有一种:跟上面差不多- void ReverseList_New(NODE** pHead)
- {
- printf("Begin to Reverse the List New \n");
- if (pHead == NULL || (*pHead)->next == NULL)
- {
- return;
- }
-
- NODE* pRev = NULL;
- NODE* pCur = *pHead;
- while(pCur != NULL)
- {
- NODE* pTemp = pCur;
- pCur = pCur->next;
- pTemp->next = pRev;
- pRev = pTemp;
- }
-
- //return pRev;//返回新的头节点
- (*pHead)->next = NULL;
- *pHead = pRev;
- }
复制代码 删除:
原文见:
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).下面见代码:- void List_DeleteNode_Google(NODE *pListHead, NODE *pToBeDeleted)
- {
- if (!pListHead || !pToBeDeleted)
- return;
-
- if (pToBeDeleted->data != NULL) {
- NODE *pNext = pToBeDeleted->next;
- pToBeDeleted->next = pNext->next;
- pToBeDeleted->data = pNext->data;
-
- delete pNext;
- pNext = NULL;
- }
- else { //待删除节点为尾节点
- NODE *pTemp = pListHead;
- while(pTemp->next != pToBeDeleted)
- pTemp = pTemp->next;
- pTemp->next = NULL;
- delete pToBeDeleted;
- pToBeDeleted = NULL;
- }
- pListHead->ListLen--;
- }
复制代码
排序
我使用了选择排序- /********************************* 链表的排序 *******************************************/
- /*
- ==========================
- 功能:选择排序(由小到大)
- 返回:指向链表表头的指针
- ==========================
-
- 选择排序的基本思想就是反复从还未排好序的那些节点中,
- 选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,
- 依次重新组合成一个链表。
-
- 我认为写链表这类程序,关键是理解:
- head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;
- 任 意一个节点p的地址,只能通过它前一个节点的next来求得。
-
- 单向链表的选择排序图示:
- ---->[1]---->[3]---->[2]...----> [n]---->[NULL](原链表)
- head 1->next 3->next 2->next n->next
-
- ---->[NULL](空链表)
- first
- tail
- ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
- first 1->next 2->next 3->next tail->next
-
- 1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;
- 2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);
- 3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;
- */
- NODE* SelectSort(PNODE *head)
- {
- if(head == NULL || *head == NULL || (*head)->next == NULL)
- return NULL;
- NODE *pfirst; /* 排列后有序链的表头指针 */
- NODE *ptail; /* 排列后有序链的表尾指针 */
- NODE *pminBefore; /* 保留键值更小的节点的前驱节点的指针 */
- NODE *pmin; /* 存储最小节点 */
- NODE *p; /* 当前比较的节点 */
-
- pfirst = NULL;
- while (*head != NULL) /*在链表中找键值最小的节点。*/
- {
- /* 注意:这里for语句就是体现选择排序思想的地方 */
- for (p = *head, pmin = *head; p->next != NULL; p = p->next) /*循环遍历链表中的节点,找出此时最小的节点。*/
- {
- if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/
- {
- pminBefore = p; /*保存找到节点的前驱节点:显然p->next的前驱节点是p。*/
- pmin = p->next; /*保存键值更小的节点。*/
- }
- }
-
- /*上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表。*/
-
- /*第一件事*/
- if (pfirst == NULL) /* 如果有序链表目前还是一个空链表 */
- {
- pfirst = pmin; /* 第一次找到键值最小的节点。 */
- ptail = pmin; /* 注意:尾指针让它指向最后的一个节点。 */
- }
- else /* 有序链表中已经有节点 */
- {
- ptail->next = pmin; /* 把刚找到的最小节点放到最后,即让尾指针的next指向它。*/
- ptail = pmin; /* 尾指针也要指向它。 */
- }
-
- /*第二件事*/
- if (pmin == *head) /* 如果找到的最小节点就是第一个节点 */
- {
- *head = (*head)->next; /* 显然让head指向原head->next,即第二个节点,就OK */
- }
- else /*如果不是第一个节点*/
- {
- pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/
- }
- }
-
- if (pfirst != NULL) /*循环结束得到有序链表first */
- {
- ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */
- }
- *head = pfirst;
- return *head;
- }
复制代码
全部代码:- #include <stdio.h>
- const int N=6;
- typedef struct _node{ //单链表
- int data;
- int ListLen;
- struct _node* next;
- }NODE,*PNODE;
- //由数组创建单链表
- PNODE CreateList(int a[N])
- {
- printf("Begin to Create the List\n");
- NODE* ListHead=new NODE();
- ListHead->data=a[0];
- ListHead->next=NULL;
- for(int i=N-1;i>=1;i--)
- {
- NODE* p=new NODE();
- p->data=a[i];
- p->ListLen = N;
- p->next=ListHead->next;
- ListHead->next=p;
- }
- //ListHead->ListLen = N;
- return ListHead;
- }
- ///输出单链表
- void PrintList(PNODE ListHead)
- {
- if(NULL==ListHead)
- {
- printf("The List is empty!");
- return;
- }
- else
- {
- NODE* p=ListHead;
- while(p!=NULL)
- {
- printf("%d ",p->data);
- p=p->next;
- }
- }
- printf("\n\n");
- }
- void ReverseList_New(NODE** pHead)
- {
- printf("Begin to Reverse the List New \n");
- if (pHead == NULL || (*pHead)->next == NULL)
- {
- return;
- }
-
- NODE* pRev = NULL;
- NODE* pCur = *pHead;
- while(pCur != NULL)
- {
- NODE* pTemp = pCur;
- pCur = pCur->next;
- pTemp->next = pRev;
- pRev = pTemp;
- }
-
- //return pRev;//返回新的头节点
- (*pHead)->next = NULL;
- *pHead = pRev;
- }
- //考虑递归算法,若只有一个结点,则直接返回,若存在两个结点(a1,a2)则需要做的操作有:
- //a2->next=a1;a1->next=NULL;return a2;
- //a2即新的头结点,若有三个结点,则应先将子链(a2,a3)先逆置且返回该子链的新的头结点,然后把子链(a2,a3)当作一个复合结点a2',
- //组成新的二元组(a1,a2')然后就可以执行前面相同的操作:a2'->next=a1;a1->next=NULL;return a3';即可,多个以上的结点可同理得到
- void ReverseList_Dg(NODE* pCur,NODE** ListHead)
- {
- if( (NULL == pCur) || (NULL == pCur->next) )
- {
- *ListHead = pCur;
- }
- else
- {
- NODE* pNext = pCur->next;
- ReverseList_Dg(pNext,ListHead); //返回后续节点的新头节点
- pNext->next = pCur; //将后继结点指向当前结点。
- pCur->next = NULL;
- }
- }
- //最好画图理解下
- void ReverseList_MF(NODE **head)
- {
- printf("Begin to Reverse the List From MallocFree\n");
- if(head == NULL ||(*head)->next == NULL || *head == NULL)
- {
- printf("This list num <= 2\n");
- return;
- }
- NODE* pPre = *head; //先前指针
- NODE* pCur = pPre->next; //当前指针
- NODE* pNext = NULL; //后继指针
- while(pCur!=NULL)
- {
- pNext = pCur->next;
- pCur->next = pPre; //把当前指向前面那个,这个时候就实现了逆向了.
- pPre = pCur;
- pCur = pNext;
- }
- (*head)->next = NULL;
- *head = pPre; //记录下新的头结点
- }
- void List_DeleNode(PNODE* list,int pos)
- {
- if( (list != NULL) && (0 <= pos) && (pos < (*list)->ListLen) )//&& ((*list)->next != NULL) )
- {
- if((*list)->next == NULL)
- {
- return;
- }
- NODE* p = *list;
- NODE *pb = NULL;
- for (int i = 0; i <= pos-1; i++) //让p指向第pos个节点,pb指向第n-1个节点
- {
- pb = p;
- p = p->next;
- }
- pb->next = p->next;//让要删除的节点的上一个节点的指针指向要删除节点的后一个节点
- //减少一个节点
- (*list)->ListLen--;
- delete[] p;
- }
- return;
- }
- PNODE list_GetNode(PNODE* list,int pos)
- {
- if( (list != NULL) && (0 <= pos) && (pos < (*list)->ListLen) )
- {
- NODE *p = *list;
- for (int i = 0; i < pos-1; i++)
- {
- p = p->next;
- }
- return p;
- }
- return NULL;
-
- }
- /*
- 一般单链表删除某个节点,需要知道删除节点的前一个节点,则需要O(n)的遍历时间,
- 显然常规思路是不行的。在仔细看题目,换一种思路,既然不能在O(1)得到删除节点的前一个元素,
- 但我们可以轻松得到后一个元素,这样,我们何不把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素。
- 可见,该方法可行,但如果待删除节点为最后一个节点,则不能按照以上思路,没有办法,只能按照常规方法遍历,时间复杂度为O(n)
- */
- void List_DeleteNode_Google(NODE *pListHead, NODE *pToBeDeleted)
- {
- if (!pListHead || !pToBeDeleted)
- return;
-
- if (pToBeDeleted->data != NULL) {
- NODE *pNext = pToBeDeleted->next;
- pToBeDeleted->next = pNext->next;
- pToBeDeleted->data = pNext->data;
-
- delete pNext;
- pNext = NULL;
- }
- else { //待删除节点为尾节点
- NODE *pTemp = pListHead;
- while(pTemp->next != pToBeDeleted)
- pTemp = pTemp->next;
- pTemp->next = NULL;
- delete pToBeDeleted;
- pToBeDeleted = NULL;
- }
- pListHead->ListLen--;
- }
- /********************************* 链表的排序 *******************************************/
- /*
- ==========================
- 功能:选择排序(由小到大)
- 返回:指向链表表头的指针
- ==========================
-
- 选择排序的基本思想就是反复从还未排好序的那些节点中,
- 选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,
- 依次重新组合成一个链表。
-
- 我认为写链表这类程序,关键是理解:
- head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;
- 任 意一个节点p的地址,只能通过它前一个节点的next来求得。
-
- 单向链表的选择排序图示:
- ---->[1]---->[3]---->[2]...----> [n]---->[NULL](原链表)
- head 1->next 3->next 2->next n->next
-
- ---->[NULL](空链表)
- first
- tail
- ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后链表)
- first 1->next 2->next 3->next tail->next
-
- 1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;
- 2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);
- 3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;
- */
- NODE* SelectSort(PNODE *head)
- {
- if(head == NULL || *head == NULL || (*head)->next == NULL)
- return NULL;
- NODE *pfirst; /* 排列后有序链的表头指针 */
- NODE *ptail; /* 排列后有序链的表尾指针 */
- NODE *pminBefore; /* 保留键值更小的节点的前驱节点的指针 */
- NODE *pmin; /* 存储最小节点 */
- NODE *p; /* 当前比较的节点 */
-
- pfirst = NULL;
- while (*head != NULL) /*在链表中找键值最小的节点。*/
- {
- /* 注意:这里for语句就是体现选择排序思想的地方 */
- for (p = *head, pmin = *head; p->next != NULL; p = p->next) /*循环遍历链表中的节点,找出此时最小的节点。*/
- {
- if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/
- {
- pminBefore = p; /*保存找到节点的前驱节点:显然p->next的前驱节点是p。*/
- pmin = p->next; /*保存键值更小的节点。*/
- }
- }
-
- /*上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表。*/
-
- /*第一件事*/
- if (pfirst == NULL) /* 如果有序链表目前还是一个空链表 */
- {
- pfirst = pmin; /* 第一次找到键值最小的节点。 */
- ptail = pmin; /* 注意:尾指针让它指向最后的一个节点。 */
- }
- else /* 有序链表中已经有节点 */
- {
- ptail->next = pmin; /* 把刚找到的最小节点放到最后,即让尾指针的next指向它。*/
- ptail = pmin; /* 尾指针也要指向它。 */
- }
-
- /*第二件事*/
- if (pmin == *head) /* 如果找到的最小节点就是第一个节点 */
- {
- *head = (*head)->next; /* 显然让head指向原head->next,即第二个节点,就OK */
- }
- else /*如果不是第一个节点*/
- {
- pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/
- }
- }
-
- if (pfirst != NULL) /*循环结束得到有序链表first */
- {
- ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */
- }
- *head = pfirst;
- return *head;
- }
- int main()
- {
- int a[N] = {5,7,2,4,10,1};
- NODE* list = CreateList(a);
- PrintList(list);
- //递归方法
- NODE* pTemp = list;
- printf("Begin to Reverse the List From Recursion \n");
- ReverseList_Dg(pTemp,&list);
- PrintList(list);
- //普通方法
- ReverseList_MF(&list);
- PrintList(list);
- //普通方法2
- ReverseList_New(&list);
- PrintList(list);
- //删除节点
- printf("Delete second nodes\n");
- List_DeleNode(&list,1);
- PrintList(list);
- //删除节点
- printf("Del Node From Google -- Delete second nodes\n");
- List_DeleteNode_Google(list,list_GetNode(&list,2));
- PrintList(list);
-
- //选择排序
- printf("SelectSort\n");
- SelectSort(&list);
- PrintList(list);
-
- getchar();
- }
复制代码 |
|