單鏈表的操作算法是筆試面試中較為常見的題目。本文將著重介紹平時面試中常見的關于鏈表的應用題目。
本文大概 一萬五千字 ，建議閱讀時間為一個小時，請先收藏再閱讀，平時也可以拿出來多看幾遍。
題目：輸入一個單鏈表，輸出此鏈表中的倒數第 K 個節點。（去除頭結點，節點計數從 1 開始）。
（1）遍歷單鏈表，遍歷同時得出鏈表長度 N 。
（2）再次從頭遍歷，訪問至第 N - K 個節點為所求節點。
/*計算鏈表長度*/
int listLength(ListNode* pHead){
int count = 0;
ListNode* pCur = pHead->next;
if(pCur == NULL){
printf('error');
}
while(pCur){
count++;
pCur = pCur->pNext;
}
return count;
}
/*查找第k個節點的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
int i = 0;
ListNode* pCur = pHead;
//計算鏈表長度
int len = listLength(pHead);
if(k > len){
printf('error');
}
//循環len-k+1次
for(i=0; i <>1; i++){
pCur = pCur->next;
}
return pCur;//返回倒數第K個節點
}
采用這種遍歷方式需要兩次遍歷鏈表，時間復雜度為O(n※2)。可見這種方式最為簡單,也較好理解，但是效率低下。
（1）定義num = k
（2）使用遞歸方式遍歷至鏈表末尾。
（3）由末尾開始返回，每返回一次 num 減 1
（4）當 num 為 0 時，即可找到目標節點
int num;//定義num值
ListNode* findKthTail(ListNode* pHead, int k) {
num = k;
if(pHead == NULL)
return NULL;
//遞歸調用
ListNode* pCur = findKthTail(pHead->next, k);
if(pCur != NULL)
return pCur;
else{
num--;// 遞歸返回一次，num值減1
if(num == 0)
return pHead;//返回倒數第K個節點
return NULL;
}
}
使用遞歸的方式實現仍然需要兩次遍歷鏈表，時間復雜度為O(n※2)。
（1）定義兩個指針 p1 和 p2 分別指向鏈表頭節點。
（2）p1 前進 K 個節點，則 p1 與 p2 相距 K 個節點。
（3）p1，p2 同時前進，每次前進 1 個節點。
（4）當 p1 指向到達鏈表末尾，由于 p1 與 p2 相距 K 個節點，則 p2 指向目標節點。
ListNode* findKthTail(ListNode *pHead, int K){
if (NULL == pHead || K == 0)
return NULL;
//p1，p2均指向頭節點
ListNode *p1 = pHead;
ListNode *p2 = pHead;
//p1先出發，前進K個節點
for (int i = 0; i <>
if (p1)//防止k大于鏈表節點的個數
p1 = p1->_next;
else
return NULL;
}
while (p1)//如果p1沒有到達鏈表結尾，則p1，p2繼續遍歷
{
p1 = p1->_next;
p2 = p2->_next;
}
return p2;//當p1到達末尾時，p2正好指向倒數第K個節點
}
可以看出使用雙指針法只需遍歷鏈表一次，這種方法更為高效時間復雜度為O(n)，通常筆試題目中要考的也是這種方法。
單鏈表中的環是指鏈表末尾的節點的 next 指針不為 NULL ，而是指向了鏈表中的某個節點，導致鏈表中出現了環形結構。
鏈表中有環示意圖：
鏈表的末尾節點 8 指向了鏈表中的節點 3，導致鏈表中出現了環形結構。
對于鏈表是否是由有環的判斷方法有哪些呢？
（1）遍歷鏈表，記錄已訪問的節點。
（2）將當前節點與之前以及訪問過的節點比較，若有相同節點則有環。
否則，不存在環。
這種窮舉比較思想簡單，但是效率過于低下，尤其是當鏈表節點數目較多，在進行比較時花費大量時間，時間復雜度大致在 O(n^2)。這種方法自然不是出題人的理想答案。如果筆試面試中使用這種方法，估計就要跪了，忘了這種方法吧。
既然在窮舉遍歷時，元素比較過程花費大量時間，那么有什么辦法可以提高比較速度呢？
（1）首先創建一個以節點 ID 為鍵的 HashSe t集合，用來存儲曾經遍歷過的節點。
（2）從頭節點開始，依次遍歷單鏈表的每一個節點。
（3）每遍歷到一個新節點，就用新節點和 HashSet 集合當中存儲的節點作比較，如果發現 HashSet 當中存在相同節點 ID，則說明鏈表有環，如果 HashSet 當中不存在相同的節點 ID，就把這個新節點 ID 存入 HashSet ，之后進入下一節點，繼續重復剛才的操作。
假設從鏈表頭節點到入環點的距離是 a ，鏈表的環長是 r 。而每一次 HashSet 查找元素的時間復雜度是 O(1), 所以總體的時間復雜度是 1 * ( a + r ) = a + r，可以簡單理解為 O(n) 。而算法的空間復雜度還是 a + r - 1，可以簡單地理解成 O(n) 。
（1）定義兩個指針分別為 slow，fast，并且將指針均指向鏈表頭節點。
（2）規定，slow 指針每次前進 1 個節點，fast 指針每次前進兩個節點。
（3）當 slow 與 fast 相等，且二者均不為空，則鏈表存在環。
無環過程：
通過圖解過程可以看出，若表中不存在環形，fast 與 slow 指針只能在鏈表末尾相遇。
有環過程：
圖解過程可以看出，若鏈表中存在環，則快慢指針必然能在環中相遇。這就好比在環形跑道中進行龜兔賽跑。由于兔子速度大于烏龜速度，則必然會出現兔子與烏龜再次相遇情況。因此，當出現快慢指針相等時，且二者不為NULL，則表明鏈表存在環。
bool isExistLoop(ListNode* pHead) {
ListNode* fast;//慢指針，每次前進一個節點
ListNode* slow;//快指針，每次前進2個節點
slow = fast = pHead ; //兩個指針均指向鏈表頭節點
//當沒有到達鏈表結尾，則繼續前進
while (slow != NULL && fast -> next != NULL) {
slow = slow -> next ; //慢指針前進一個節點
fast = fast -> next -> next ; //快指針前進兩個節點
if (slow == fast) //若兩個指針相遇，且均不為NULL則存在環
return true ;
}
//到達末尾仍然沒有相遇，則不存在環
return false ;
}
在 3.1 節中，已經實現了鏈表中是否有環的判斷方法。那么，當鏈表中存在環，如何確定環的入口節點呢？
slow 指針每次前進一個節點，故 slow 與 fast 相遇時，slow 還沒有遍歷完整個鏈表。設 slow 走過節點數為 s，fast 走過節點數為 2s。設環入口點距離頭節點為 a，slow 與 fast 首次相遇點距離入口點為 b，環的長度為 r。
則有：
s = a + b;
2s = n * r + a + b; n 代表fast指針已經在環中循環的圈數。
則推出：
s = n * r; 意味著slow指針走過的長度為環的長度整數倍。
若鏈表頭節點到環的末尾節點度為 L，slow 與 fast 的相遇節點距離環入口節點為 X。
則有：
a+X = s = n * r = (n - 1) * r + (L - a);
a = (n - 1) * r + (L - a - X);
上述等式可以看出：
從 slow 與 fast 相遇點出發一個指針 p1，請進 (L - a - X) 步，則此指針到達入口節點。同時指針 p2 從頭結點出發，前進 a 步。當 p1 與 p2 相遇時，此時 p1 與 p2 均指向入口節點。
例如圖3.1所示鏈表：
slow 走過節點 s = 6；
fast 走過節點 2s = 12；
環入口節點據流頭節點 a = 3；
相遇點距離頭節點 X = 3；
L = 8；
r = 6；
可以得出 a = (n - 1) * r + (L - a - X)結果成立。
//找到環中的相遇節點
ListNode* getMeetingNode(ListNode* pHead) // 假設為帶頭節點的單鏈表
{
ListNode* fast;//慢指針，每次前進一個節點
ListNode* slow;//快指針，每次前進2個節點
slow = fast = pHead ; //兩個指針均指向鏈表頭節點
//當沒有到達鏈表結尾，則繼續前進
while (slow != NULL && fast -> next != NULL){
slow = slow -> next ; //慢指針前進一個節點
fast = fast -> next -> next ; //快指針前進兩個節點
if (slow == fast) //若兩個指針相遇，且均不為NULL則存在環
return slow;
}
//到達末尾仍然沒有相遇，則不存在環
return NULL ;
}
//找出環的入口節點
ListNode* getEntryNodeOfLoop(ListNode* pHead){
ListNode* meetingNode = getMeetingNode(pHead); // 先找出環中的相遇節點
if (meetingNode == NULL)
return NULL;
ListNode* p1 = meetingNode;
ListNode* p2 = pHead;
while (p1 != p2) // p1和p2以相同的速度向前移動，當p2指向環的入口節點時，p1已經圍繞著環走了n圈又回到了入口節點。
{
p1 = p1->next;
p2 = p2->next;
}
//返回入口節點
return p1;
}
在3.1中找到了 slow 與 fast 的相遇節點，令 solw 與 fast 指針從相遇節點出發，按照之前的前進規則，當 slow 與fast 再次相遇時，slow 走過的長度正好為環的長度。
int getLoopLength(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
while ( fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if ( slow == fast )//第一次相遇
break;
}
//slow與fast繼續前進
slow = slow->next;
fast = fast->next->next;
int length = 1; //環長度
while ( fast != slow )//再次相遇
{
slow = slow->next;
fast = fast->next->next;
length ++; //累加
}
//當slow與fast再次相遇，得到環長度
return length;
}
兩個用鏈表代表的整數，其中每個節點包含一個數字。數字存儲按照在原來整數中相反的順序，使得第一個數字位于鏈表的開頭。寫出一個函數將兩個整數相加，用鏈表形式返回和。
例如：
輸入：
3->1->5->null
5->9->2->null，
輸出：
8->0->8->null
ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
ListNode *ret = l1, *pre = l1;
int up = 0;
while (l1 != NULL && l2 != NULL) {
//數值相加
l1->val = l1->val + l2->val + up;
//計算是否有進位
up = l1->val / 10;
//保留計算結果的個位
l1->val %= 10;
//記錄當前節點位置
pre = l1;
//同時向后移位
l1 = l1->next;
l2 = l2->next;
}
//若l1到達末尾，說明l1長度小于l2
if (l1 == NULL)
//pre->next指向l2的當前位置
pre->next = l2;
//l1指針指向l2節點當前位置
l1 = pre->next;
//繼續計算剩余節點
while (l1 != NULL) {
l1->val = l1->val + up;
up = l1->val / 10;
l1->val %= 10;
pre = l1;
l1 = l1->next;
}
//最高位計算有進位，則新建一個節點保留最高位
if (up != 0) {
ListNode *tmp = new ListNode(up);
pre->next = tmp;
}
//返回計算結果鏈表
return ret;
}
題目：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例：
輸入：
1->2->4,
1->3->4
輸出：
1->1->2->3->4->4
（1）對空鏈表存在的情況進行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。（兩個都為空此情況在pHead1為空已經被攔截）
（2）在兩個鏈表無空鏈表的情況下確定第一個結點，比較鏈表1和鏈表2的第一個結點的值，將值小的結點保存下來為合并后的第一個結點。并且把第一個結點為最小的鏈表向后移動一個元素。
（3）繼續在剩下的元素中選擇小的值，連接到第一個結點后面，并不斷next將值小的結點連接到第一個結點后面，直到某一個鏈表為空。
（4）當兩個鏈表長度不一致時，也就是比較完成后其中一個鏈表為空，此時需要把另外一個鏈表剩下的元素都連接到第一個結點的后面。
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* pTail = NULL;//指向新鏈表的最后一個結點 pTail->next去連接
ListNode* newHead = NULL;//指向合并后鏈表第一個結點
if (NULL == pHead1){
return pHead2;
}else if(NULL == pHead2){
return pHead1;
}else{
//確定頭指針
if ( pHead1->data < phead2->data){
newHead = pHead1;
pHead1 = pHead1->next;//指向鏈表的第二個結點
}else{
newHead = pHead2;
pHead2 = pHead2->next;
}
pTail = newHead;//指向第一個結點
while ( pHead1 && pHead2) {
if ( pHead1->data <= phead2->data ){
pTail->next = pHead1;
pHead1 = pHead1->next;
}else {
pTail->next = pHead2;
pHead2 = pHead2->next;
}
pTail = pTail->next;
}
if(NULL == pHead1){
pTail->next = pHead2;
}else if(NULL == pHead2){
pTail->next = pHead1;
}
return newHead;
}
（1）對空鏈表存在的情況進行處理，假如 pHead1 為空則返回 pHead2 ，pHead2 為空則返回 pHead1。
（2）比較兩個鏈表第一個結點的大小，確定頭結點的位置
（3）頭結點確定后，繼續在剩下的結點中選出下一個結點去鏈接到第二步選出的結點后面，然后在繼續重復（2 ）（3） 步，直到有鏈表為空。
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* newHead = NULL;
if (NULL == pHead1){
return pHead2;
}else if(NULL ==pHead2){
return pHead2;
}else{
if (pHead1->data < phead2->data){
newHead = pHead1;
newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
}else{
newHead = pHead2;
newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
}
return newHead;
}
}
給定一個單鏈表中的表頭和一個等待被刪除的節點。請在 O(1) 時間復雜度刪除該鏈表節點。并在刪除該節點后，返回表頭。
示例：
給定 1->2->3->4，和節點 3，返回 1->2->4。
在之前介紹的單鏈表刪除節點中，最普通的方法就是遍歷鏈表，復雜度為O(n)。
如果我們把刪除節點的下一個結點的值賦值給要刪除的結點，然后刪除這個結點，這相當于刪除了需要刪除的那個結點。因為我們很容易獲取到刪除節點的下一個節點，所以復雜度只需要O(1)。
示例
單鏈表：1->2->3->4->NULL
若要刪除節點 3 。第一步將節點3的下一個節點的值4賦值給當前節點。變成 1->2->4->4->NULL，然后將就 4 這個結點刪除，就達到目的了。 1->2->4->NULL
如果刪除的節點的是頭節點，把頭結點指向 NULL。
如果刪除的節點的是尾節點，那只能從頭遍歷到頭節點的上一個結點。
void deleteNode(ListNode **pHead, ListNode* pDelNode) {
if(pDelNode == NULL)
return;
if(pDelNode->next != NULL){
ListNode *pNext = pDelNode->next;
//下一個節點值賦給待刪除節點
pDelNode->val = pNext->val;
//待刪除節點指針指后面第二個節點
pDelNode->next = pNext->next;
//刪除待刪除節點的下一個節點
delete pNext;
pNext = NULL;
}else if(*pHead == pDelNode)//刪除的節點是頭節點
{
delete pDelNode;
pDelNode= NULL;
*pHead = NULL;
} else//刪除的是尾節點
{
ListNode *pNode = *pHead;
while(pNode->next != pDelNode) {
pNode = pNode->next;
}
pNode->next = NULL;
delete pDelNode;
pDelNode= NULL;
}
}
輸入一個鏈表，按鏈表值從尾到頭的順序返回一個 ArrayList 。
初看題目意思就是輸出的時候鏈表尾部的元素放在前面，鏈表頭部的元素放在后面。這不就是 先進后出，后進先出 么。
什么數據結構符合這個要求？
棧 ！
class Solution {
public:
vectorint> printListFromTailToHead(ListNode* head) {
vectorint> value;
ListNode *p=NULL;
p=head;
stackint> stk;
while(p!=NULL){
stk.push(p->val);
p=p->next;
}
while(!stk.empty()){
value.push_back(stk.top());
stk.pop();
}
return value;
}
};
第二種方法也比較容易想到，通過鏈表的構造，如果將末尾的節點存儲之后，剩余的鏈表處理方式還是不變，所以可以使用遞歸的形式進行處理。
class Solution {
public:
vectorint> value;
vectorint> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p!=NULL){
if(p->next!=NULL){
printListFromTailToHead(p->next);
}
value.push_back(p->val);
}
return value;
}
};
反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？
設置三個節點pre、cur、next
（1）每次查看cur節點是否為NULL，如果是，則結束循環，獲得結果
（2）如果cur節點不是為NULL，則先設置臨時變量next為cur的下一個節點
（3）讓cur的下一個節點變成指向pre，而后pre移動cur，cur移動到next
（4）重復（1）（2）（3）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 遞歸終止條件
if(head == NULL || head->next == NULL)
return head;
ListNode* rhead = reverseList(head->next);
// head->next此刻指向head后面的鏈表的尾節點
// head->next->next = head把head節點放在了尾部
head->next->next = head;
head->next = NULL;
return rhead;
}
};
