19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

Description

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.

說明：
給定的 n 保證是有效的。

Analyze

給定的函數(shù)如下:

• @param head 鏈表頭結(jié)點(diǎn)(帶數(shù)據(jù))
• @param n 一個(gè)整數(shù)，表示要刪除的倒數(shù)第 n 個(gè)結(jié)點(diǎn)
• @return 鏈表頭結(jié)點(diǎn)

這題按基本解法的話就是先遍歷鏈表，找到鏈表的總個(gè)數(shù)，在定位到倒數(shù)第 n-1 個(gè)結(jié)點(diǎn)，然后刪除下一個(gè)結(jié)點(diǎn)。但是在考慮這種解法的時(shí)后可以這么想，當(dāng)我第一次遍歷鏈表的時(shí)候能不能把第二次遍歷的事情給做了，因?yàn)閮纱味际潜闅v嘛，所以看看能不能變成一次，也就是我想在第一次遍歷的時(shí)候就找到倒數(shù)第 n-1 個(gè)結(jié)點(diǎn)，當(dāng)你用一個(gè)指針遍歷到鏈表最后一個(gè)結(jié)點(diǎn)的時(shí)候，我怎么得到我要的那個(gè)節(jié)點(diǎn)呢?答案是在用一個(gè)指針指向倒數(shù)第n-1個(gè)結(jié)點(diǎn)就行了，即使用快慢指針解決。我們只只要用兩個(gè)指針，一開始同時(shí)指向第一個(gè)結(jié)點(diǎn)，然后讓一個(gè)結(jié)點(diǎn)先出發(fā)n-1個(gè)結(jié)點(diǎn)，那么等這個(gè)結(jié)點(diǎn)到達(dá)末尾時(shí)，后面的結(jié)點(diǎn)剛好落后n-1個(gè)結(jié)點(diǎn)，這樣只需遍歷一次鏈表就行了。

Realization

• 定義

給鏈表定義一個(gè)頭指針以便適應(yīng)更廣泛的情況，比如當(dāng)要刪除的結(jié)點(diǎn)是第一個(gè)時(shí)，沒有頭指針的話將很難把這種情況合并到循環(huán)里面去，而是要作為特殊情況另外處理。不過也不是說定了頭指針就完美了，由于多了一個(gè)頭指針，上述分析的定位到倒數(shù)第n-1個(gè)結(jié)點(diǎn)就要修改一下了，這里應(yīng)該是修改為直接定位到倒數(shù)第n個(gè)(相當(dāng)于原來n個(gè)結(jié)點(diǎn)變成n-1個(gè)了)。

• 先出發(fā)的結(jié)點(diǎn)

  
  

• 主循環(huán)

  
  

• 刪除結(jié)點(diǎn)

  
  

• 返回

  
  

• 提交

  
  

附源代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* pre = head, *last;
    struct ListNode h;
    h.next = head;
    last = &h;
    while(n--)
    {
        pre = pre->next;
    }   
    while(pre)
    {
        pre = pre->next;
        last = last->next;
    }
    last->next = last->next->next;
    return h.next;
}