删除链表倒数第 n 个结点
题目描述
- 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.
来源：力扣（LeetCode）
链接：力扣网19题
说明：给定的 n 保证是有效的。
题解
思路：使用两个指针，第一个指针遍历n次，第二个指针指向链表头结点，此时，两个指针同时向后遍历，第一个指针到达终点时第二个指针指向的就是倒数第n个结点的位置。
解释：因为倒数加其对应的正数的和就是链表的总长度加一。所以，一个指针先遍历倒数的值，再向后遍历的链表尾节点的过程就是正数值，此时另一个指针从头结点遍历，该指针的终点就是倒数第n个结点。
代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//构造结构体
typedef struct list
{
int data;
struct list *next;
}*List,LNode;
//函数声明
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);
}
//删除链表倒数第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;
}
//链表初始化函数
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;
}
//链表输出函数
void print_list(List head)
{
List p;
p = head;
while(p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
