[算法练习]逆置链表,链表排序,删除节点
逆置：使用递归
//考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（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来求得。
单向链表的选择排序图示：
---->---->---->...----> ---->（原链表）
head 1->next3->next2->next n->next
---->（空链表）
first
tail
---->---->---->...---->---->（排序后链表）
first 1->next2->next3->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)
{
printf("Begin to Create the List\n");
NODE* ListHead=new NODE();
ListHead->data=a;
ListHead->next=NULL;
for(int i=N-1;i>=1;i--)
{
NODE* p=new NODE();
p->data=a;
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来求得。
单向链表的选择排序图示：
---->---->---->...----> ---->（原链表）
head 1->next3->next2->next n->next
---->（空链表）
first
tail
---->---->---->...---->---->（排序后链表）
first 1->next2->next3->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 = {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();
}
页:
[1]