刪除鏈表倒數(shù)第 n 個(gè)結(jié)點(diǎn)
題目描述
- 給定一個(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.
來源：力扣（LeetCode）
鏈接：力扣網(wǎng)19題
說明：給定的 n 保證是有效的九孩。
題解
思路：使用兩個(gè)指針，第一個(gè)指針遍歷n次发框，第二個(gè)指針指向鏈表頭結(jié)點(diǎn)躺彬，此時(shí)，兩個(gè)指針同時(shí)向后遍歷缤底，第一個(gè)指針到達(dá)終點(diǎn)時(shí)第二個(gè)指針指向的就是倒數(shù)第n個(gè)結(jié)點(diǎn)的位置顾患。
解釋：因?yàn)榈箶?shù)加其對(duì)應(yīng)的正數(shù)的和就是鏈表的總長(zhǎng)度加一。所以个唧，一個(gè)指針先遍歷倒數(shù)的值江解，再向后遍歷的鏈表尾節(jié)點(diǎn)的過程就是正數(shù)值，此時(shí)另一個(gè)指針從頭結(jié)點(diǎn)遍歷徙歼，該指針的終點(diǎn)就是倒數(shù)第n個(gè)結(jié)點(diǎn)犁河。
代碼
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//構(gòu)造結(jié)構(gòu)體
typedef struct list
{
int data;
struct list *next;
}*List,LNode;
//函數(shù)聲明
List init_list(List head,int num);
void print_list(List head);
List delNode(List head,int num);
void main()
{
List head;
head = (List)malloc(sizeof(LNode));
head = init_list(head,5);
print_list(head);
head = delNode(head,5);
print_list(head);
}
//刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
List delNode(List head,int n)
{
List p,q;
p = head;
q = head;
if(head->next == NULL)
return NULL;
while(p->next != NULL)
{
if(n > 0)
{
p = p->next;
n--;
}
else
{
p = p->next;
q = q->next;
}
}
if(n == 1)
return head->next;
q->next = q->next->next;
return head;
}
//鏈表初始化函數(shù)
List init_list(List head,int num)
{
int i = 1;
List p = head;
while(i <= num)
{
List s;
s = (LNode*)malloc(sizeof(LNode));
s->data = rand() % 100 + 1;
s->next = NULL;
p->next = s;
p = p->next;
i++;
}
return head->next;
}
//鏈表輸出函數(shù)
void print_list(List head)
{
List p;
p = head;
while(p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
