1、合并兩個(gè)有序鏈表

解題思路

使用虛擬頭結(jié)點(diǎn)

遍歷兩個(gè)鏈表，將數(shù)值小的節(jié)點(diǎn)加入虛擬頭節(jié)點(diǎn)中。直到某個(gè)鏈表為空。將另一個(gè)鏈表加入。

返回虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

當(dāng)你需要?jiǎng)?chuàng)造一條新鏈表的時(shí)候，可以使用虛擬頭結(jié)點(diǎn)簡(jiǎn)化邊界情況的處理

2、單鏈表的分解

解題思路

創(chuàng)建兩個(gè)虛擬頭節(jié)點(diǎn)，分別存放小于鏈表和大于等于鏈表

遍歷鏈表，小于的加入鏈表，大于等于的加入另一個(gè)鏈表

遍歷兩個(gè)鏈表虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

然后連接兩個(gè)鏈表

3、合并k個(gè)有序鏈表

1的加強(qiáng)型，其實(shí)先從k個(gè)鏈表中找到第一個(gè)最小的就行，可以使用最小堆。然后使用1的套路

4、單鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn) 刪除鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)

雙指針，第一個(gè)指針先走k步，然后第二個(gè)指針指向頭，兩個(gè)指針相差k。兩個(gè)指針同時(shí)往前走。

當(dāng)?shù)谝粋€(gè)指針到尾部的時(shí)候，第二個(gè)指針剛好在倒數(shù)第k個(gè)節(jié)點(diǎn)。

5、單鏈表的中點(diǎn)

快慢指針，一個(gè)指針走1步，一個(gè)指針走2步。當(dāng)走兩步的指針到尾部時(shí)，另一個(gè)指針就到中間。

6、判斷鏈路是否包含環(huán)

快慢指針，慢指針走1步，快指針走2步，如果快指針最后指向空，說明沒有環(huán)，如果快慢指針相遇，說明有環(huán)。

7、兩個(gè)鏈表是否相交

將兩個(gè)鏈表相連，同時(shí)遍歷兩個(gè)鏈表就可以同時(shí)進(jìn)入公共部分

具體代碼見知乎

https://zhuanlan.zhihu.com/p/599759514