leetCode-0019_删除链表的倒数第N个节点

Posted on | In |

题目描述

英文题目

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

中文题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解决方法

方法一
  • 描述

我们需要用两个指针来帮助我们解题，fast和slow指针。首先fast指针先向前走N步，如果此时slow指向空，说明N为链表的长度，则需要移除的为首元素，那么此时我们返回head->next即可，如果slow存在，我们再继续往下走，此时fast指针也跟着走，直到slow为最后一个元素时停止，此时fast指向要移除元素的前一个元素，我们再修改指针跳过需要移除的元素即可

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 删除链表的倒数第N个节点
 
 @param head 不带头结点
 @param n 倒数第N个节点
 @return 删除后的链表
 */
struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
    if (!head->next) {
        return NULL;
    }
    
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    
    if (!fast) {
        return head->next;
    }
    
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    
    struct ListNode *temp = slow->next;
    slow->next = temp->next;
    
    free(temp);
    
    return head;
}


/**
 删除链表的倒数第N个节点测试
 */
void removeNthFromEnd_test()
{
    SingleLinkListNode *head = single_link_list_create();
    single_link_list_insert_tail(head, 1);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 3);
    single_link_list_insert_tail(head, 4);
    single_link_list_insert_tail(head, 5);
    
    
    printf("========删除链表的倒数第N个节点测试========\n");
    single_link_list_dump_head(head);
    SingleLinkListNode *new = removeNthFromEnd(head->next, 2);
    single_link_list_dump(new);
}

题目来源

Remove Nth Node From End of List

删除链表的倒数第N个节点

线性表相关代码

数据结构-线性表