題目如下：
給定一個鏈表，洗掉鏈表的倒數第 n 個節點，并且回傳鏈表的頭結點，
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當洗掉了倒數第二個節點后，鏈表變為 1->2->3->5.
解題思路：
1、計算鏈表的長度，洗掉倒數第n個，就是洗掉倒數第len%n個節點
2、快慢指標均指向頭結點，慢指標在頭結點處不動，快指標向后走n個節點
3、如果此時快指標指向空，就是意味著要洗掉的是第一個結點，return head->next；即完成洗掉操作，如果此時快指標不為空，那么快慢指標開始一起向后走，直到快指標到達最后一個節點位置，此時的慢指標指向的就是要洗掉結點的前驅結點了，執行q->next = q->next->next;//洗掉結點
ListNode *removeNthFromEnd(ListNode *head, int n)
{
if (head == NULL || n <= 0)
return head;
ListNode *p = head;
ListNode *q = head;
int len = 0;//定義len記錄鏈表的長度
while (p != NULL)//計算鏈表的長度
{
len++;
p = p->next;
}
n = n % len;//求出最簡n
p = head;//p回到頭結點
while (p != NULL && n--)//p往后走n個結點
{
p = p->next;
}
if (p == NULL)//說明要洗掉的那個結點是第一個結點
return head->next;
while (p->next != NULL)//p,q一起往后走
{
p = p->next;
q = q->next;
}
q->next = q->next->next;//洗掉結點
return head;//回傳頭結點即回傳新鏈表
}
代碼運行圖如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252050.html
標籤：其他
上一篇：C++類的封裝 | 類的封裝