如何使用C++實(shí)現(xiàn)單鏈表刪除倒數(shù)第k個節(jié)點(diǎn)的方法

這篇文章主要介紹如何使用C++實(shí)現(xiàn)單鏈表刪除倒數(shù)第k個節(jié)點(diǎn)的方法，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

具體如下：

題目：

刪除單鏈表中倒數(shù)第k個節(jié)點(diǎn)

解題思路及算法代碼：

標(biāo)尺法，定義兩個指針指向鏈表頭結(jié)點(diǎn)，先讓一個走k步，然后兩個指針同時(shí)開始走，當(dāng)先走的指針走到末尾時(shí)，后走的指針指向的結(jié)點(diǎn)就是需要刪除的結(jié)點(diǎn)。

單鏈表結(jié)構(gòu)定義：

typedef struct Node
{
  int data;
  struct Node* next;
}node, *pLinkedList;

刪除倒數(shù)第K結(jié)點(diǎn)操作代碼：

//head表示頭結(jié)點(diǎn)
Node* removeLastKthNode(pLinkedList head, int k)
{
  if (NULL == head->next || k < 1)
    return head;
  pLinkedList cur = head; //1號指針
  pLinkedList ret = head; //2號指針，指向待刪除節(jié)點(diǎn)
  pLinkedList pre = NULL; //pdel待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
  /*
  head  1  2  3  4  5
  cur
  ret
  */
  while (k > 0 && cur != NULL)
  {
    k--;
    cur = cur->next;
  }
  //當(dāng)鏈表走到終點(diǎn)時(shí)，k仍然大于0，可知k值大于鏈表長度
  if (k > 0 && cur == NULL)
  {
    cout << "k值大于鏈表長度" << endl;
    return head;
  }
  //k == 0時(shí)，1號指針和2號指針同時(shí)走,ret即為待刪除的節(jié)點(diǎn)
  if (k == 0)
  {
    while (cur != NULL)
    {
      pre = ret;
      cur = cur->next;
      ret = ret->next;
    }
    /*k = 2時(shí)
    head  1    2   3    4   5  NULL
               pre   ret     cur
    即要求刪除ret節(jié)點(diǎn)
    */
    pre->next = ret->next;
    free(ret);
    ret = NULL;
    return head;
  }
}

以上是“如何使用C++實(shí)現(xiàn)單鏈表刪除倒數(shù)第k個節(jié)點(diǎn)的方法”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！