<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    <del id="afajh"><form id="afajh"></form></del>
        1. <th id="afajh"><progress id="afajh"></progress></th>
          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>

          【41期】盤點(diǎn)那些必問的數(shù)據(jù)結(jié)構(gòu)算法題之鏈表

          共 11519字,需瀏覽 24分鐘

           ·

          2020-09-19 11:02

          程序員的成長(zhǎng)之路
          互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?
          關(guān)注


          閱讀本文大概需要 11?分鐘。

          來自:juejin.im/post/5b8a0e99f265da43320730ba

          0 概述

          鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),在很多地方會(huì)用到。如在Linux內(nèi)核代碼,redis源碼,python源碼中都有使用。除了單向鏈表,還有雙向鏈表,本文主要關(guān)注單向鏈表(含部分循環(huán)鏈表題目,會(huì)在題目中注明,其他情況都是討論簡(jiǎn)單的單向鏈表)。雙向鏈表在redis中有很好的實(shí)現(xiàn),也在我的倉庫中拷貝了一份用于測(cè)試用,本文的相關(guān)代碼在 這里。
          https://github.com/shishujuan/data-structure-algorithms

          1 定義

          先定義一個(gè)單向鏈表結(jié)構(gòu),如下,定義了鏈表結(jié)點(diǎn)和鏈表兩個(gè)結(jié)構(gòu)體。這里我沒有多定義一個(gè)鏈表的結(jié)構(gòu)體,保存頭指針,尾指針,鏈表長(zhǎng)度等信息,目的也是為了多練習(xí)下指針的操作。
          //?aslist.h

          //?鏈表結(jié)點(diǎn)定義
          typedef?struct?ListNode?{
          ????struct?ListNode?*next;
          ????int?value;
          }?listNode;

          2 基本操作

          在上一節(jié)的鏈表定義基礎(chǔ)上,我們完成幾個(gè)基本操作函數(shù),包括鏈表初始化,鏈表中添加結(jié)點(diǎn),鏈表中刪除結(jié)點(diǎn)等。
          /**
          ?*?創(chuàng)建鏈表結(jié)點(diǎn)
          ?*/

          ListNode?*listNewNode(int?value)
          {
          ????ListNode?*node;
          ????if?(!(node?=?malloc(sizeof(ListNode))))
          ????????return?NULL;

          ????node->value?=?value;
          ????node->next?=?NULL;
          ????return?node;
          }

          /**
          ?*?頭插法插入結(jié)點(diǎn)。
          ?*/

          ListNode?*listAddNodeHead(ListNode?*head,?int?value)
          {
          ????ListNode?*node;
          ????if?(!(node?=?listNewNode(value)))
          ????????return?NULL;

          ????if?(head)?
          ????????node->next?=?head;

          ????head?=?node;
          ????return?head;
          }

          /**
          ?*?尾插法插入值為value的結(jié)點(diǎn)。
          ?*/

          ListNode?*listAddNodeTail(ListNode?*head,?int?value)
          {
          ????ListNode?*node;
          ????if?(!(node?=?listNewNode(value)))
          ????????return?NULL;

          ????return?listAddNodeTailWithNode(head,?node);
          }

          /**
          ?*?尾插法插入結(jié)點(diǎn)。
          ?*/

          ListNode?*listAddNodeTailWithNode(ListNode?*head,?ListNode?*node)
          {
          ????if?(!head)?{
          ????????head?=?node;
          ????}?else?{
          ????????ListNode?*current?=?head;
          ????????while?(current->next)?{
          ????????????current?=?current->next;
          ????????}?
          ????????current->next?=?node;
          ????}
          ????return?head;
          }

          /**
          ?*?從鏈表刪除值為value的結(jié)點(diǎn)。
          ?*/

          ListNode?*listDelNode(ListNode?*head,?int?value)
          {
          ????ListNode?*current=head,?*prev=NULL;

          ????while?(current)?{
          ????????if?(current->value?==?value)?{
          ????????????if?(current?==?head)
          ????????????????head?=?head->next;

          ????????????if?(prev)
          ????????????????prev->next?=?current->next;

          ????????????free(current);
          ????????????break;
          ????????}

          ????????prev?=?current;
          ????????current?=?current->next;
          ????}
          ????return?head;
          }

          /**
          ?*?鏈表遍歷。
          ?*/

          void?listTraverse(ListNode?*head)
          {
          ????ListNode?*current?=?head;
          ????while?(current)?{
          ????????printf("%d",?current->value);
          ????????printf("->");
          ????????current?=?current->next;
          ????????if?(current?==?head)?//?處理首尾循環(huán)鏈表情況
          ????????????break;
          ????}

          ????printf("NULL\n");
          }

          /**
          ?*?使用數(shù)組初始化一個(gè)鏈表,共len個(gè)元素。
          ?*/

          ListNode?*listCreate(int?a[],?int?len)
          {
          ????ListNode?*head?=?NULL;
          ????int?i;
          ????for?(i?=?0;?i?????????if?(!(head?=?listAddNodeTail(head,?a[i])))
          ????????????return?NULL;
          ????}
          ????return?head;
          }

          /**
          *?鏈表長(zhǎng)度函數(shù)
          */

          int?listLength(ListNode?*head)
          {
          ????int?len?=?0;
          ????while?(head)?{
          ????????len++;
          ????????head?=?head->next;
          ????}
          ????return?len;
          }

          3 鏈表相關(guān)面試題

          3.1 鏈表逆序

          題:?給定一個(gè)單向鏈表 1->2->3->NULL,逆序后變成 3->2->1->NULL。
          解:常見的是用的循環(huán)方式對(duì)各個(gè)結(jié)點(diǎn)逆序連接,如下:
          /**
          ?*?鏈表逆序,非遞歸實(shí)現(xiàn)。
          */
          ListNode?*listReverse(ListNode?*head)
          {
          ????ListNode?*newHead?=?NULL,?*current?=?head;
          ????while?(current)?{
          ????????ListNode?*next?=?current->next;
          ????????current->next?=?newHead;
          ????????newHead?=?current;
          ????????current?=?next;
          ????}

          ????return?newHead;
          }
          如果帶點(diǎn)炫技性質(zhì)的,那就來個(gè)遞歸的解法,如下:
          /**
          ?*?鏈表逆序,遞歸實(shí)現(xiàn)。
          ?*/

          ListNode?*listReverseRecursive(ListNode?*head)
          {
          ????if?(!head?||?!head->next)?{
          ????????return?head;
          ????}

          ????ListNode?*reversedHead?=?listReverseRecursive(head->next);
          ????head->next->next?=?head;
          ????head->next?=?NULL;
          ????return?reversedHead;
          }

          3.2 鏈表復(fù)制

          題:?給定一個(gè)單向鏈表,復(fù)制并返回新的鏈表頭結(jié)點(diǎn)。
          解:同樣可以有兩種解法,非遞歸和遞歸的,如下:
          /**
          ?*?鏈表復(fù)制-非遞歸
          ?*/

          ListNode?*listCopy(ListNode?*head)?
          {
          ????ListNode?*current?=?head,?*newHead?=?NULL,?*newTail?=?NULL;?
          ????while?(current)?{
          ????????ListNode?*node?=?listNewNode(current->value);
          ????????if?(!newHead)?{?//?第一個(gè)結(jié)點(diǎn)
          ????????????newHead?=?newTail?=?node;
          ????????}?else?{
          ????????????newTail->next?=?node;
          ????????????newTail?=?node;
          ????????}
          ????????current?=?current->next;
          ????}
          ????return?newHead;
          }

          /**
          ?*?鏈表復(fù)制-遞歸
          ?*/

          ListNode?*listCopyRecursive(ListNode?*head)
          {
          ????if?(!head)?
          ????????return?NULL;

          ????ListNode?*newHead?=?listNewNode(head->value);
          ????newHead->next?=?listCopyRecursive(head->next);
          ????return?newHead;
          }

          3.3 鏈表合并

          題:?已知兩個(gè)有序單向鏈表,請(qǐng)合并這兩個(gè)鏈表,使得合并后的鏈表仍然有序(注:這兩個(gè)鏈表沒有公共結(jié)點(diǎn),即不交叉)。如鏈表1是 1->3->4->NULL,鏈表2是 2->5->6->7->8->NULL,則合并后的鏈表為 1->2->3->4->5->6->7->8->NULL。
          解:這個(gè)很類似歸并排序的最后一步,將兩個(gè)有序鏈表合并到一起即可。使用2個(gè)指針分別遍歷兩個(gè)鏈表,將較小值結(jié)點(diǎn)歸并到結(jié)果鏈表中。如果一個(gè)鏈表歸并結(jié)束后另一個(gè)鏈表還有結(jié)點(diǎn),則把另一個(gè)鏈表剩下部分加入到結(jié)果鏈表的尾部。代碼如下所示:
          /**
          ?*?鏈表合并-非遞歸
          ?*/

          ListNode?*listMerge(ListNode?*list1,?ListNode?*list2)
          {
          ????ListNode?dummy;?//?使用空結(jié)點(diǎn)保存合并鏈表
          ????ListNode?*tail?=?&dummy;

          ????if?(!list1)
          ????????return?list2;

          ????if?(!list2)
          ????????return?list1;

          ????while?(list1?&&?list2)?{
          ????????if?(list1->value?<=?list2->value)?{
          ????????????tail->next?=?list1;
          ????????????tail?=?list1;
          ????????????list1?=?list1->next;
          ????????}?else?{
          ????????????tail->next?=?list2;
          ????????????tail?=?list2;
          ????????????list2?=?list2->next;
          ????????}
          ????}

          ????if?(list1)?{
          ????????tail->next?=?list1;
          ????}?else?if?(list2)?{
          ????????tail->next?=?list2;
          ????}

          ????return?dummy.next;
          }
          當(dāng)然,要實(shí)現(xiàn)一個(gè)遞歸的也不難,代碼如下:
          ListNode?*listMergeRecursive(ListNode?*list1,?ListNode?*list2)
          {
          ????ListNode?*result?=?NULL;

          ????if?(!list1)
          ????????return?list2;

          ????if?(!list2)
          ????????return?list1;

          ????if?(list1->value?<=?list2->value)?{
          ????????result?=?list1;
          ????????result->next?=?listMergeRecursive(list1->next,?list2);
          ????}?else?{
          ????????result?=?list2;
          ????????result->next?=?listMergeRecursive(list1,?list2->next);
          ????}

          ????return?result;
          }

          3.4 鏈表相交判斷

          題:?已知兩個(gè)單向鏈表list1,list2,判斷兩個(gè)鏈表是否相交。如果相交,請(qǐng)找出相交的結(jié)點(diǎn)。
          解1:可以直接遍歷list1,然后依次判斷l(xiāng)ist1每個(gè)結(jié)點(diǎn)是否在list2中,但是這個(gè)解法的復(fù)雜度為 O(length(list1) * length(list2))。當(dāng)然我們可以遍歷list1時(shí),使用哈希表存儲(chǔ)list1的結(jié)點(diǎn),這樣再遍歷list2即可判斷了,時(shí)間復(fù)雜度為O(length(list1) + length(list2)),空間復(fù)雜度為 O(length(list1)),這樣相交的結(jié)點(diǎn)自然也就找出來了。當(dāng)然,找相交結(jié)點(diǎn)還有更好的方法。
          解2:兩個(gè)鏈表如果相交,那么它們從相交后的節(jié)點(diǎn)一定都是相同的。假定list1長(zhǎng)度為len1,list2長(zhǎng)度為len2,且 len1 > len2,則我們只需要將 list1 先遍歷 len1-len2個(gè)結(jié)點(diǎn),然后兩個(gè)結(jié)點(diǎn)一起遍歷,如果遇到相等結(jié)點(diǎn),則該結(jié)點(diǎn)就是第一個(gè)相交結(jié)點(diǎn)。
          /**
          ?*?鏈表相交判斷,如果相交返回相交的結(jié)點(diǎn),否則返回NULL。
          ?*/

          ListNode?*listIntersect(ListNode?*list1,?ListNode?*list2)
          {
          ????int?len1?=?listLength(list1);
          ????int?len2?=?listLength(list2);
          ????int?delta?=?abs(len1?-?len2);

          ????ListNode?*longList?=?list1,?*shortList?=?list2;

          ????if?(len1?????????longList?=?list2;
          ????????shortList?=?list1;
          ????}

          ????int?i;
          ????for?(i?=?0;?i?????????longList?=?longList->next;
          ????}

          ????while?(longList?&&?shortList)?{
          ????????if?(longList?==?shortList)
          ????????????return?longList;

          ????????longList?=?longList->next;
          ????????shortList?=?shortList->next;
          ????}

          ????return?NULL;
          }

          3.5 判斷鏈表是否存在環(huán)

          題:?給定一個(gè)鏈表,判斷鏈表中是否存在環(huán)。
          解1:容易想到的方法就是使用一個(gè)哈希表記錄出現(xiàn)過的結(jié)點(diǎn),遍歷鏈表,如果一個(gè)結(jié)點(diǎn)重復(fù)出現(xiàn),則表示該鏈表存在環(huán)。如果不用哈希表,也可以在鏈表結(jié)點(diǎn) ListNode 結(jié)構(gòu)體中加入一個(gè) visited字段做標(biāo)記,訪問過標(biāo)記為1,也一樣可以檢測(cè)。由于目前我們還沒有實(shí)現(xiàn)一個(gè)哈希表,這個(gè)方法代碼后面再加。
          解2:更好的一種方法是 Floyd判圈算法,該算法最早由羅伯特.弗洛伊德發(fā)明。通過使用兩個(gè)指針fast和slow遍歷鏈表,fast指針每次走兩步,slow指針每次走一步,如果fast和slow相遇,則表示存在環(huán),否則不存在環(huán)。(注意,如果鏈表只有一個(gè)節(jié)點(diǎn)且沒有環(huán),不會(huì)進(jìn)入while循環(huán))
          /**
          ?*?檢測(cè)鏈表是否有環(huán)-Flod判圈算法
          ?*?若存在環(huán),返回相遇結(jié)點(diǎn),否則返回NULL
          ?*/

          ListNode?*listDetectLoop(ListNode?*head)
          {
          ????ListNode?*slow,?*fast;
          ????slow?=?fast?=?head;

          ????while?(slow?&&?fast?&&?fast->next)?{
          ????????slow?=?slow->next;
          ????????fast?=?fast->next->next;
          ????????if?(slow?==?fast)?{
          ????????????printf("Found?Loop\n");
          ????????????return?slow;
          ????????}
          ????}

          ????printf("No?Loop\n");
          ????return?NULL;
          }

          void?testListDetectLoop()
          {
          ????printf("\nTestListDetectLoop\n");
          ????int?a[]?=?{1,?2,?3,?4};
          ????ListNode?*head?=?listCreate(a,?ALEN(a));
          ????listDetectLoop(head);

          ????//?構(gòu)造一個(gè)環(huán)
          ????head->next->next->next?=?head;
          ????listDetectLoop(head);
          }
          擴(kuò)展:檢測(cè)到有環(huán)的話,那要如何找鏈表的環(huán)的入口點(diǎn)呢?
          首先,我們來證明一下為什么上面的解2提到的算法是正確的。如果鏈表不存在環(huán),因?yàn)榭熘羔樏看巫?步,必然會(huì)比慢指針先到達(dá)鏈表尾部,不會(huì)相遇。
          如果存在環(huán),假定快慢指針經(jīng)過s次循環(huán)后相遇,則此時(shí)快指針走的距離為 2s,慢指針走的距離為 s,假定環(huán)內(nèi)結(jié)點(diǎn)數(shù)為r,則要相遇則必須滿足下面條件,即相遇時(shí)次數(shù)滿足 s = nr。即從起點(diǎn)之后下一次相遇需要循環(huán) r 次。
          2s?-?s?=?nr?=>?s?=?nr
          環(huán)長(zhǎng)度r=4,則從起點(diǎn)后下一次相遇需要經(jīng)過4次循環(huán)。
          那么環(huán)的入口點(diǎn)怎么找呢?前面已經(jīng)可知道第一次相遇要循環(huán) r 次,而相遇時(shí)慢指針走的距離為 s=r,設(shè)鏈表總長(zhǎng)度為L(zhǎng),鏈表頭到環(huán)入口的距離為a,環(huán)入口到相遇點(diǎn)的距離為x,則L = a + r,可以推導(dǎo)出 a = (L-x-a),其中L-x-a為相遇點(diǎn)到環(huán)入口點(diǎn)的距離,即鏈表頭到環(huán)入口的距離a等于相遇點(diǎn)到環(huán)入口距離。
          s?=?r?=?a?+?x?=>?a?+?x?=?(L-a)?=>?a?=?L-x-a
          于是,在判斷鏈表存在環(huán)后,從相遇點(diǎn)和頭結(jié)點(diǎn)分別開始遍歷,兩個(gè)指針每次都走一步,當(dāng)兩個(gè)指針相等時(shí),就是環(huán)的入口點(diǎn)。
          /**
          ?*?查找鏈表中環(huán)入口
          ?*/

          ListNode?*findLoopNode(ListNode?*head)
          {
          ????ListNode?*meetNode?=?listDetectLoop(head);
          ????if?(!meetNode)
          ????????return?NULL;

          ????ListNode?*headNode?=?head;
          ????while?(meetNode?!=?headNode)?{
          ????????meetNode?=?meetNode->next;
          ????????headNode?=?headNode->next;
          ????}
          ????return?meetNode;
          }

          3.6 鏈表模擬加法

          題:?給定兩個(gè)鏈表,每個(gè)鏈表的結(jié)點(diǎn)值為數(shù)字的各位上的數(shù)字,試求出兩個(gè)鏈表所表示數(shù)字的和,并將結(jié)果以鏈表形式返回。假定兩個(gè)鏈表分別為list1和list2,list1各個(gè)結(jié)點(diǎn)值分別為數(shù)字513的個(gè)位、十位和百位上的數(shù)字,同理list2的各個(gè)結(jié)點(diǎn)值為數(shù)字295的各位上的數(shù)字。則這兩個(gè)數(shù)相加為808,所以輸出按照從個(gè)位到百位順序輸出,返回的結(jié)果鏈表如下。
          list1:??(3?->?1?->?5?->?NULL)

          list2:??(5?->?9?->?2?->?NULL)

          result:?(8?->?0?->?8?->?NULL)
          解:這個(gè)題目比較有意思,需要對(duì)鏈表操作比較熟練。我們考慮兩個(gè)數(shù)字相加過程,從低位到高位依次相加,如果有進(jìn)位則標(biāo)記進(jìn)位標(biāo)志,直到最高位才終止。設(shè)當(dāng)前位的結(jié)點(diǎn)為current,則有:
          current->data?=?list1->data?+?list2->data?+?carry
          (其中carry為低位的進(jìn)位,如果有進(jìn)位為1,否則為0)
          非遞歸代碼如下:
          /**
          ?*?鏈表模擬加法-非遞歸解法
          ?*/

          ListNode?*listEnumarateAdd(ListNode?*list1,?ListNode?*list2)
          {
          ????int?carry?=?0;
          ????ListNode?*result?=?NULL;

          ????while?(list1?||?list2?||?carry)?{
          ????????int?value?=?carry;
          ????????if?(list1)?{
          ????????????value?+=?list1->value;
          ????????????list1?=?list1->next;
          ????????}

          ????????if?(list2)?{
          ????????????value?+=?list2->value;
          ????????????list2?=?list2->next;
          ????????}

          ????????result?=?listAddNodeTail(result,?value?%?10);
          ????????carry?=?(?value?>=?10???1:?0);
          ????}

          ????return?result;
          }
          非遞歸實(shí)現(xiàn)如下:
          /**
          ?*?鏈表模擬加法-遞歸解法
          ?*/

          ListNode?*listEnumarateAddRecursive(ListNode?*list1,?ListNode?*list2,?int?carry)
          {
          ????if?(!list1?&&?!list2?&&?carry==0)
          ????????return?NULL;

          ????int?value?=?carry;
          ????if?(list1)
          ????????value?+=?list1->value;

          ????if?(list2)
          ????????value?+=?list2->value;

          ????ListNode?*next1?=?list1???list1->next?:?NULL;
          ????ListNode?*next2?=?list2???list2->next?:?NULL;
          ????ListNode?*more?=?listEnumarateAddRecursive(next1,?next2,?(value?>=?10???1?:?0));
          ????ListNode?*result?=?listNewNode(carry);
          ????result->value?=?value?%?10;
          ????result->next?=?more;

          ????return?result;
          }

          3.7 有序單向循環(huán)鏈表插入結(jié)點(diǎn)

          題:?已知一個(gè)有序的單向循環(huán)鏈表,插入一個(gè)結(jié)點(diǎn),仍保持鏈表有序,如下圖所示。
          解:在解決這個(gè)問題前,我們先看一個(gè)簡(jiǎn)化版本,就是在一個(gè)有序無循環(huán)的單向鏈表中插入結(jié)點(diǎn),仍然保證其有序。這個(gè)問題的代碼相信多數(shù)人都很熟悉,一般都是分兩種情況考慮:
          • 如果原來鏈表為空或者插入的結(jié)點(diǎn)值最小,則直接插入該結(jié)點(diǎn)并設(shè)置為頭結(jié)點(diǎn)。

          • 如果原來鏈表非空,則找到第一個(gè)大于該結(jié)點(diǎn)值的結(jié)點(diǎn),并插入到該結(jié)點(diǎn)的前面。如果插入的結(jié)點(diǎn)值最大,則插入在尾部。

          實(shí)現(xiàn)代碼如下:
          /**
          ?*?簡(jiǎn)化版-有序無循環(huán)鏈表插入結(jié)點(diǎn)
          ?*/

          ListNode?*sortedListAddNode(ListNode?*head,?int?value)
          {
          ????ListNode?*node?=?listNewNode(value);
          ????if?(!head?||?head->value?>=?value)?{?//情況1
          ????????node->next?=?head;
          ????????head?=?node;
          ????}?else?{??//情況2
          ????????ListNode?*current?=?head;
          ????????while?(current->next?!=?NULL?&&?current->next->value?????????????current?=?current->next;
          ????????node->next?=?current->next;
          ????????current->next?=?node;
          ????}
          ????return?head;
          }
          當(dāng)然這兩種情況也可以一起處理,使用二級(jí)指針。如下:
          /**
          ?*?簡(jiǎn)化版-有序無循環(huán)鏈表插入結(jié)點(diǎn)(兩種情況一起處理)
          ?*/

          void?sortedListAddNodeUnify(ListNode?**head,?int?value)
          {
          ????ListNode?*node?=?listNewNode(value);
          ????ListNode?**current?=?head;
          ????while?((*current)?&&?(*current)->value?value)?{
          ????????current?=?&((*current)->next);
          ????}
          ????node->next?=?*current;
          ????*current?=?node;
          }
          接下來看循環(huán)鏈表的情況,其實(shí)也就是需要考慮下面2點(diǎn):
          1) prev->value ≤ value ≤ current->value:
          插入到prev和current之間。
          2) value為最大值或者最小值:
          插入到首尾交接處,如果是最小值重新設(shè)置head值。
          代碼如下:
          /**
          ?*?有序循環(huán)鏈表插入結(jié)點(diǎn)
          ?*/

          ListNode?*sortedLoopListAddNode(ListNode?*head,?int?value)
          {
          ????ListNode?*node?=?listNewNode(value);
          ????ListNode?*current?=?head,?*prev?=?NULL;
          ????do?{
          ????????prev?=?current;
          ????????current?=?current->next;
          ????????if?(value?>=?prev->value?&&?value?<=?current->value)
          ????????????break;
          ????}?while?(current?!=?head);

          ????prev->next?=?node;
          ????node->next?=?current;

          ????if?(current?==?head?&&?value?value)?//?判斷是否要設(shè)置鏈表頭
          ????????head?=?node;

          ????return?head;
          }

          3.8 輸出鏈表倒數(shù)第K個(gè)結(jié)點(diǎn)

          題:?給定一個(gè)簡(jiǎn)單的單向鏈表,輸出鏈表的倒數(shù)第K個(gè)結(jié)點(diǎn)。
          解1:如果是順數(shù)第K個(gè)結(jié)點(diǎn),不用多思考,直接遍歷即可。這個(gè)題目的新意在于它是要輸出倒數(shù)第K個(gè)結(jié)點(diǎn)。一個(gè)直觀的想法是,假定鏈表長(zhǎng)度為L(zhǎng),則倒數(shù)第K個(gè)結(jié)點(diǎn)就是順數(shù)的 L-K+1 個(gè)結(jié)點(diǎn)。如鏈表長(zhǎng)度為3,倒數(shù)第2個(gè),就是順數(shù)的第2個(gè)結(jié)點(diǎn)。這樣需要遍歷鏈表2次,一次求長(zhǎng)度,一次找結(jié)點(diǎn)。
          /**
          *?鏈表倒數(shù)第K個(gè)結(jié)點(diǎn)-遍歷兩次算法
          */

          ListNode?*getLastKthNodeTwice(ListNode?*head,?int?k)
          {
          ????int?len?=?listLength(head);?????
          ????if?(k?>?len)
          ????????return?NULL;

          ????ListNode?*current?=?head;?
          ????int?i;
          ????for?(i?=?0;?i?len-k;?i++)??//遍歷鏈表,找出第N-K+1個(gè)結(jié)點(diǎn)
          ????????current?=?current->next;

          ????return?current;
          }
          解2:當(dāng)然更好的一種方法是遍歷一次,設(shè)置兩個(gè)指針p1,p2,首先p1和p2都指向head,然后p2向前走k步,這樣p1和p2之間就間隔k個(gè)節(jié)點(diǎn)。最后p1和p2同時(shí)向前移動(dòng),p2走到鏈表末尾的時(shí)候p1剛好指向倒數(shù)第K個(gè)結(jié)點(diǎn)。代碼如下:
          /**
          *?鏈表倒數(shù)第K個(gè)結(jié)點(diǎn)-遍歷一次算法
          */

          ListNode?*getLastKthNodeOnce(ListNode?*head,?int?k)
          {
          ????ListNode?*p1,?*p2;
          ????p1?=?p2?=?head;

          ????for(;?k?>?0;?k--)?{
          ????????if?(!p2)?//?鏈表長(zhǎng)度不夠K
          ????????????return?NULL;
          ????????p2?=?p2->next;
          ????}

          ????while?(p2)?{
          ????????p1?=?p1->next;
          ????????p2?=?p2->next;
          ????}
          ????return?p1;
          }

          推薦閱讀:

          【40期】說一下線程池內(nèi)部工作原理

          【39期】Mybatis面試18問,你想知道的都在這里了!

          【38期】一份tcp、http面試指南,常考點(diǎn)都給你了

          最近開始整理《100期Java面試題匯總》PDF版本,目前整理到第20期,3.6W詞,想獲取的可以先加我微信,后續(xù)整理完會(huì)在朋友圈通知如何獲取。

          長(zhǎng)按二維碼,添加我微信

          朕已閱?

          瀏覽 42
          點(diǎn)贊
          評(píng)論
          收藏
          分享

          手機(jī)掃一掃分享

          分享
          舉報(bào)
          評(píng)論
          圖片
          表情
          推薦
          點(diǎn)贊
          評(píng)論
          收藏
          分享

          手機(jī)掃一掃分享

          分享
          舉報(bào)
          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            <del id="afajh"><form id="afajh"></form></del>
                1. <th id="afajh"><progress id="afajh"></progress></th>
                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  无码国产激情视频 | 日本无码无卡二三 | 久草视频在线免费看 | 五月天婷婷精品视频 | 精品人妻一区二区三区奶水 |