数据结构与算法之美，课后习题：07|链表（下）：单链表练习题汇总

摘要: 最新学习前google工程师王争大佬的《数据结构与算法之美》，07|链表（下），他觉得，写链表是最考验逻辑思维能力的。我附议哈哈，课后习题如下

1.单链表反转。

2.两个有序的链表合并。（同时升序或者同时降序）

3.删除链表倒数第n个结点。

4.求链表的中间节点。

5.链表中环的检测。

最好是自己动手编程，再对比下，如果有不足之处一定要留言啊，互相学习。

1.单链表反转。

 1 void ReverseList(Node * pHead)
 2 {
 3     if(!pHead || !pHead->pNext)
 4     {
 5         return;
 6     }
 7     Node * pPrev = NULL;
 8     Node * pTemp = NULL;
 9     Node * pTravel = pHead->pNext;
10     while (pTravel->pNext)
11     {
12         pTemp = pTravel;
13         pTravel = pTravel->pNext;
14         pTemp->pNext = pPrev;
15         pPrev = pTemp;
16     }
17     pTravel->pNext = pPrev;
18     pHead->pNext = pTravel;
19 }

View Code

2.两个有序的链表合并。

说明：有好多例子把两个链表尾部接过去，我觉得不妥的原因：1.破坏原有链表结构，如果下面还有函数想使用怎么办。2.如果下面不再使用了，如何回收无用链表的节点，此时节点已经交错了。

 1 //合并2个降序的单链表
 2 void MergeOrderList(Node * pNewList, Node * pList1, Node * pList2)
 3 {
 4     if (!pNewList || !pList1 || !pList2)
 5     {
 6         return;
 7     }
 8     Node * pTempList1 = pList1->pNext;
 9     Node * pTempList2 = pList2->pNext;
10     while(pTempList1 && pTempList2)
11     {
12         if(pTempList1->a > pTempList2->a)
13         {
14             pNewList->pNext = new Node(pTempList1->a);
15             pNewList = pNewList->pNext;
16             pTempList1 = pTempList1->pNext;
17         }
18         else
19         {
20             pNewList->pNext = new Node(pTempList2->a);
21             pNewList = pNewList->pNext;
22             pTempList2 = pTempList2->pNext;
23         }
24     }
25     while (pTempList1)
26     {
27         pNewList->pNext = new Node(pTempList1->a);
28         pNewList = pNewList->pNext;
29         pTempList1 = pTempList1->pNext;
30     }
31     while (pTempList2)
32     {
33         pNewList->pNext = new Node(pTempList2->a);
34         pNewList = pNewList->pNext;
35         pTempList2 = pTempList2->pNext;
36     }
37 }

View Code

3.删除链表倒数第n个结点。

 1 //删除倒数第N个节点
 2 void DelLastN(Node * pHead, int nLast)
 3 {
 4     if (!pHead)
 5     {
 6         return;
 7     }
 8     Node * pSlow = pHead;
 9     Node * pFast = pHead;
10     for (int i = 0; i<nLast; ++i)
11     {
12         if (!pFast->pNext)
13         {
14             return;
15         }
16         pFast = pFast->pNext;
17     }
18     while (pFast->pNext)
19     {
20         pFast = pFast->pNext;
21         pSlow = pSlow->pNext;
22     }
23     Node * pDel = NULL;
24     pDel = pSlow->pNext;
25     pSlow->pNext = pDel->pNext;
26     delete pDel;
27 }

View Code

4.求链表的中间节点。

 1 //求链表的中间节点
 2 Node * GetMiddle(Node * pHead)
 3 {
 4     if (!pHead)
 5     {
 6         return NULL;
 7     }
 8     Node * pSlow = pHead;
 9     Node * pFast = pHead;
10     while (pFast && pFast->pNext)
11     {
12         pFast = pFast->pNext->pNext;
13         pSlow = pSlow->pNext;
14     }
15     return pSlow;
16 }

View Code

5.链表中环的检测。

没想好

数据结构与算法之美，课后习题：07|链表（下）：单链表练习题汇总

推荐阅读