删除单链表中倒数第k个结点c语言
时间: 2023-12-12 10:05:25 浏览: 26
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode *fast = head, *slow = head;
for(int i = 0; i < n; i++){
fast = fast->next;
}
if(fast == NULL){ //需要删除的是头结点
head = head->next;
free(slow);
return head;
}
while(fast->next != NULL){
fast = fast->next;
slow = slow->next;
}
struct ListNode* temp = slow->next;
slow->next = slow->next->next;
free(temp);
return head;
}
相关问题
删除单链表中倒数第k个结点
A:要删除单链表中倒数第k个结点,可以使用双指针法。首先定义两个指针,一个指针先走 k 步,然后再让第二个指针和第一个指针一起走,当第一个指针指向链表尾部时,第二个指针指向的就是倒数第 k 个结点的前一个结点。
接下来,只需要将第二个指针指向的结点的 next 指针指向倒数第 k 个结点的下一个结点即可。
具体代码实现如下:
```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
first = dummy
second = dummy
for i in range(n):
first = first.next
while first.next is not None:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next
```
这里使用了 dummy 结点,它的作用是防止第二个指针指向空结点,在链表只有一个结点并且要删除时特别有用。
删除单链表中倒数第k个结点(简化)c语言
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *fast = head, *slow = head;
// fast指针先走n步
for (int i = 0; i < n; i++) {
fast = fast->next;
}
// 如果fast指针已经到了链表尾部,说明要删除的是头结点
if (fast == NULL) {
head = head->next;
free(slow);
return head;
}
// 同时移动fast和slow指针,直到fast到达链表尾部
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第n个结点
struct ListNode* tmp = slow->next;
slow->next = slow->next->next;
free(tmp);
return head;
}