19. Remove Nth Node From End of List

发表于 | 分类于

每日一题 2019 - 03 - 10

题目:

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个元素，直观的思路就是：

  • 先遍历一遍整个链表找出元素个数
  • 遍历过程中找到对应位置的元素删除

可以换个思路，我们使用两个指针cur、pre，其中cur比pre先行n步，当cur到达末尾时，pre所指的下一个元素即是要删除的元素，这样就可以保证我们的复杂度最低，时间复杂度也有所下降。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *cur = head, *pre = head;
        while(n--) cur = cur->next;
        if(cur == NULL) return head->next;
        while(cur->next) {
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = pre->next->next;
        return head;
    }
};
0%
undefined