【C語言】單鏈表的相關熱點面試題（包括：從尾到頭打印，逆置，冒泡，尋找中間節點，倒數k節點）

https://blog.csdn.net/hanjing_1995/article/details/51539599

  1. 從尾到頭打印單鏈表

[cpp]?view plaincopy
  1. void?FromTailToHeadPrint(SListNode*&?head)??
  2. {??
  3. ????stack<SListNode*>?s;??
  4. ????SListNode*?cur?=?head;??
  5. ????while?(cur)??
  6. ????{??
  7. ????????s.push(cur);??
  8. ????????cur?=?cur->_next;??
  9. ????}??
  10. ??
  11. ????while?(!s.empty())??
  12. ????{??
  13. ????????cout?<<?s.top()->_data?<<"->";??
  14. ????????s.pop();??
  15. ????}??
  16. ????cout?<<?""<<endl;??
  17. }??



2.刪除一個無頭單鏈表的非尾節點

[cpp]?view plaincopy
  1. void?Erase(SListNode*&?head,SListNode*?pos)??
  2. {??
  3. ????//分情況：空節點、一個節點、兩個節點、三個節點??
  4. ????if?(head?==?NULL?||?pos==NULL)??
  5. ????{??
  6. ????????return;??
  7. ????}??
  8. ??????
  9. ????if?(head?==?pos)??
  10. ????{??
  11. ????????free(head);??
  12. ????????head?=?NULL;??
  13. ????????return;??
  14. ????}??
  15. ??
  16. ????SListNode*?cur?=?head;??
  17. ????while?(cur)??
  18. ????{??
  19. ????????SListNode*?next?=?cur->_next;??
  20. ??????????
  21. ????????if?(next?==?pos)??
  22. ????????{??
  23. ????????????//若只有兩個節點，pos=next,nextnext=NULL，cur->_next?=?nextnext;??
  24. ????????????//（即使題設未說明刪除非尾節點）依然可以刪除成功。??
  25. ????????????SListNode*?nextnext?=?next->_next;??
  26. ????????????cur->_next?=?nextnext;??
  27. ????????????free(next);??
  28. ????????????next?=?NULL;??
  29. ????????}??
  30. ????????cur?=?cur->_next;??
  31. ????}??
  32. }??



3.逆置、反轉單鏈表

[cpp]?view plaincopy
  1. void?Reverse(SListNode*&?head)??
  2. {??
  3. ????if?(head?==?NULL)??
  4. ????{??
  5. ????????return;??
  6. ????}??
  7. ????SListNode*?cur?=?head;??
  8. ????SListNode*?next?=?NULL;??
  9. ????while?(cur)??
  10. ????{??
  11. ????????SListNode*?tmp?=?cur;??
  12. ????????cur?=?cur->_next;??
  13. ????????tmp->_next?=?next;??
  14. ????????next?=?tmp;??
  15. ????????head?=?tmp;??
  16. ????}??
  17. }??



4.單鏈表冒泡排序

[cpp]?view plaincopy
  1. void?BubbleSort(SListNode*&?head)??
  2. {??
  3. ????//空節點或一個節點直接返回??
  4. ????if?(head?==?NULL?||?head->_next?==?NULL)??
  5. ????{??
  6. ????????return;??
  7. ????}??
  8. ??????
  9. ????SListNode*?begin?=?head;??
  10. ????SListNode*?cur?=?head;??
  11. ??
  12. ????while?(begin->_next)??
  13. ????{??????????
  14. ????????while?(cur->_next)??
  15. ????????{??
  16. ????????????if?(cur->_data?>?cur->_next->_data)??
  17. ????????????{??
  18. ????????????????swap(cur->_data,?cur->_next->_data);??
  19. ????????????}??
  20. ????????????cur?=?cur->_next;??
  21. ????????}??
  22. ????????begin?=?begin->_next;??
  23. ????}??
  24. }??



5.查找單鏈表的中間節點，要求只能遍歷一次鏈表

[cpp]?view plaincopy
  1. SListNode*?FindMiddle(SListNode*&?head)??
  2. {??
  3. ????if?(head?==?NULL)??
  4. ????{??
  5. ????????return?NULL;??
  6. ????}??
  7. ????SListNode*?slow?=?head;??
  8. ????SListNode*?fast?=?head;??
  9. ??
  10. ????while?(fast->_next)??
  11. ????{??
  12. ????????if?(fast->_next)??
  13. ????????{??
  14. ????????????fast?=?fast->_next;??
  15. ????????????if?(fast->_next)??
  16. ????????????{??
  17. ????????????????fast?=?fast->_next;??
  18. ????????????}??
  19. ????????????else??
  20. ????????????{??
  21. ????????????????return?slow;??
  22. ????????????}??
  23. ????????????slow?=?slow->_next;??
  24. ????????}??
  25. ????????else??
  26. ????????{??
  27. ????????????return?NULL;??
  28. ????????}??
  29. ????}??
  30. ??????
  31. ????return?slow;??
  32. }??



6.查找單鏈表的倒數第k個節點，要求只能遍歷一次鏈表

[cpp]?view plaincopy
  1. SListNode*?FindLastK(SListNode*&?head,int?k)??
  2. {??
  3. ????assert(k?>?0);??
  4. ????if?(head?==?NULL)??
  5. ????{??
  6. ????????return?NULL;??
  7. ????}??
  8. ????SListNode*?slow?=?head;??
  9. ????SListNode*?fast?=?head;??
  10. ????while?(k--)??
  11. ????{??
  12. ????????if?(fast->_next)??
  13. ????????{??
  14. ????????????fast?=?fast->_next;??
  15. ????????}??
  16. ????????else??
  17. ????????{??
  18. ????????????return?NULL;??
  19. ????????}??
  20. ????}??
  21. ????slow?=?slow->_next;??
  22. ????while?(fast->_next)??
  23. ????{??
  24. ????????fast?=?fast->_next;??
  25. ????????slow?=?slow->_next;??
  26. ????}??
  27. ????return?slow;??
  28. }??


本文出自 “Han Jing's Blog” 博客，請務必保留此出處http://10740184.blog.51cto.com/10730184/1772313



本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383733.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383733.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383733.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Linux命令【二】終端+Vim

Linux命令【二】終端+Vim

需要先安裝net-tools ifconfig eth0 網卡&#xff0c;硬件地址為MAC 地址&#xff0c;網卡編號&#xff0c;絕對不會重復 lo 回環地址 測試兩臺主機之間能否通信&#xff1a;ping IP或域名 [-c 4//回饋四條信息 -i//每隔多少秒回饋一次] 得到域名對應的IPnslookup 域名得到域…
閱讀更多...
Linux如何將文件中內容放到粘貼板上

Linux如何將文件中內容放到粘貼板上

沒有找到如何在vim中將內容復制到粘貼板上&#xff0c;只找到了使用另一個軟件進行操作。 首先安裝xsel sudo apt-get install xsel # 將剪切板中的內容輸出到文件 echo $(xsel --clipboard) >> a.txt# 將文件的內容復制到剪切板 cat a.txt | xsel --clipboard
閱讀更多...
【C語言】str類與men庫函數的實現（如：strcpy,strcmp,strstr,strcat,memmove,memcpy)

【C語言】str類與men庫函數的實現（如：strcpy,strcmp,strstr,strcat,memmove,memcpy)

https://blog.csdn.net/hanjing_1995/article/details/51539583strcpy拷貝源字符串到子字符串&#xff0c;包括‘\0’。代碼實現&#xff1a;[cpp] view plaincopychar* strcpy(char* dst,const char* src) { assert(src); char* ret dst; while (*src) …
閱讀更多...
【筆試常考】C語言：深度剖析strlen,sizeof

【筆試常考】C語言：深度剖析strlen,sizeof

https://blog.csdn.net/hanjing_1995/article/details/51539532在之前的博客中&#xff0c;我也探索過strlen,sizeof區別&#xff0c;詳情可見博客http://10740184.blog.51cto.com/10730184/1705820。關于strlen,sizeof均可求字符串長度&#xff0c;這兩者是筆試面試常考的知識…
閱讀更多...
vim環境配置 +vimplus配置

vim環境配置 +vimplus配置

vim配置 參考網站&#xff1a;傳送門 這個網站詳細說明了vim配置的命令&#xff0c;我挑選了我想要用的部分&#xff0c;自己配置了一下。 配置vim的文件有兩個&#xff0c;一個是/etc/vim/vimrc 這個是系統配置文件&#xff0c;修改這個文件將會修改所有用戶的vim環境&…
閱讀更多...
劍指offer面試題：替換空格

劍指offer面試題：替換空格

https://blog.csdn.net/yanxiaolx/article/details/52235212題目&#xff1a;請實現一個函數&#xff0c;把字符串中的每個空格替換成“%20”。例如輸入“We are happy.”&#xff0c;則輸出“We%20are%20happy.”。解析&#xff1a;時間復雜度為O(n)的解法。完整代碼及測試用例…
閱讀更多...
數據庫原理及應用【一】引言

數據庫原理及應用【一】引言

什么是數據庫&#xff1a;一個大規模的集成的數據集合 作用&#xff1a;描述現實世界的實體(entities)以及實體之間的關系 管理數據庫的系統軟件&#xff1a;DBMS 文件是一個平滑的字符流&#xff0c;無法完成信息的檢索和管理 數據&#xff08;data&#xff09;:用來描述現…
閱讀更多...
Linux命令【三】gcc編譯＋靜態庫＋動態庫＋makefile+gdb調試

Linux命令【三】gcc編譯＋靜態庫＋動態庫＋makefile+gdb調試

用C編譯器編譯源文件&#xff1a;gcc 源文件 -o 可執行文件名 詳細步驟&#xff1a; gcc -E a.c -o a.i預處理器將頭文件展開&#xff0c;宏替換&#xff0c;去掉注釋gcc -S a.i -o a.s編譯器將C文件變成匯編文件gcc -c a.s -o a.o匯編器將會變文件變成二進制文件gcc a.o -o a…
閱讀更多...
用c++模擬實現一個學生成績管理系統

用c++模擬實現一個學生成績管理系統

https://blog.csdn.net/yanxiaolx/article/details/53393437題目&#xff1a;用c模擬實現一個學生成績的信息管理系統&#xff0c;要求能添加、刪除、修改、查看和保存學生的信息等功能 源代碼如下:[cpp] view plaincopy#define _CRT_SECURE_NO_WARNINGS #include<iostr…
閱讀更多...
Linux命令【四】文件+虛擬內存+常用系統函數

Linux命令【四】文件+虛擬內存+常用系統函數

File*其實是一個結構體 文件描述符FD&#xff1a;索引到對應的磁盤文件文件讀寫位置指針FP_POS&#xff0c;如果同時讀寫需要注意文件指針的位置I/O緩沖區BUFFER&#xff1a;保存內存指針&#xff0c;默認大小是8kb&#xff0c;用于減小我們對硬盤操作的次數。因為我們對硬盤的…
閱讀更多...
Python3列表

Python3列表

操作&#xff1a;索引、切片、加、乘、檢查成員、確定序列長度、確定最大最小元素 定義&#xff1a; 列表名 [元素]下標列表名[x] 截取:列表名[x:y] 更新&#xff1a; list[x]y 或者使用append()方法添加列表項刪除&#xff1a; del list[x]常用操作&#xff1a; 截取與…
閱讀更多...
Linux驚群效應詳解（最詳細的了吧）

Linux驚群效應詳解（最詳細的了吧）

https://blog.csdn.net/lyztyycode/article/details/78648798?locationNum6&fps1 linux驚群效應詳細的介紹什么是驚群&#xff0c;驚群在線程和進程中的具體表現&#xff0c;驚群的系統消耗和驚群的處理方法。1、驚群效應是什么&#xff1f;驚群效應也有人叫做雷鳴群體效應…
閱讀更多...
epoll原理詳解（最清晰）

epoll原理詳解（最清晰）

https://blog.csdn.net/lyztyycode/article/details/79491419我只是把內容搬運過來做個記錄&#xff0c;方便自己以后回頭看。第一部分&#xff1a;select和epoll的任務關鍵詞&#xff1a;應用程序 文件句柄 用戶態 內核態 監控者要比較epoll相比較select高效在什么地方&#x…
閱讀更多...
Linux命令【五】系統函數

Linux命令【五】系統函數

系統文件函數 stat函數 指針如果沒有const一般表示傳出參數&#xff0c;如果加const表示傳入參數 struct stat dev_t　st_dev文件設備編號ino_t st_ino節點 inode號是唯一的&#xff0c;每個inode節點的大小一般是128字節活著256字節&#xff0c;一般文件每2KB就設置一個ino…
閱讀更多...
生產者-消費者模型的兩種實現方式

生產者-消費者模型的兩種實現方式

https://www.cnblogs.com/caolicangzhu/p/7086176.html本文主要來總結生產者-消費者模型的代碼實現,至于其原理,請大家自行百度. 一、基于鏈表的生產-消費模型(條件變量)我們以鏈表為例,生產者進行頭部插入,消費者進行頭部刪除,因此,先將鏈表相關操作封裝為LinkList.h,具體代碼…
閱讀更多...
Linux系統【一】CPU+MMU+fork函數創建進程

Linux系統【一】CPU+MMU+fork函數創建進程

切板中的內容輸出到文件### 進程相關概念 程序&#xff1a;編譯好的二進制文件&#xff0c;在磁盤上&#xff0c;不占用系統資源&#xff08;不包括磁盤&#xff09;。&#xff08;劇本&#xff09; 進程&#xff1a;占用系統資源&#xff0c;是程序的一次運行。&#xff08;戲…
閱讀更多...
Ubuntu卸載軟件

Ubuntu卸載軟件

用過使用dpkg軟件管理工具得到所有已經安裝的軟件&#xff0c;如果不清楚軟件的全名可以使用grep命令進行查找 然后再使用sudo apt-get remove --purge 軟件名卸載軟件&#xff08;--purge參數會刪除配置文件&#xff0c;刪的干凈一些&#xff09; 例如&#xff1a;
閱讀更多...
一個重要且實用的signal---SIGCHLD

一個重要且實用的signal---SIGCHLD

https://blog.csdn.net/lyztyycode/article/details/78150805SIGCHLD(修改)因為筆者之前的文章里面有錯誤&#xff0c;今天發現&#xff0c;立馬做個修改。在下面我的一段關于sigchld信號相對于直接調用wait函數的好處時&#xff0c;我說調用wait函數要一直檢測子進程是否執行完…
閱讀更多...
數據結構實驗之鏈表七：單鏈表中重復元素的刪除

數據結構實驗之鏈表七：單鏈表中重復元素的刪除

https://blog.csdn.net/blessingxry/article/details/794455111.知識點&#xff1a;逆序建立鏈表&#xff0b;節點刪除 2.題意&#xff1a;按照數據輸入的相反順序&#xff08;逆位序&#xff09;建立一個單鏈表&#xff0c;并將單鏈表中重復的元素刪除&#xff08;值相同的元素…
閱讀更多...
Python3函數和代碼復用

Python3函數和代碼復用

函數的定義 def 函數名([參數列表]):注釋函數體注意事項 函數形參不需要聲明類型&#xff0c;可以使用return語句在結束函數執行的同時返回任意類型的值&#xff0c;函數返回值類型與return語句返回表達式i的類型一致 即使該函數不需要接受任何參數&#xff0c;也必須保留一堆…
閱讀更多...
最新文章

Copyright @ 2022~2023