LeetCode笔记-19-链表删除倒数第n个结点

发表于 | 分类于

问题

Remove Nth Node From End of List

删除链表中倒数第n个元素，n始终合法，要求一次遍历

解决思路

1、最初想法

使用快慢指针（quick、slow），初始话时均指向第一个结点，然后快指针比满指针领先n个位置。

当快指针指向尾结点时(quick->next == NULL)，slow->next即是待删除结点。代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow = head,*quick =head;
        ListNode *newhead = new ListNode(-1);
        newhead->next = slow;
        if(!head->next) 
            return NULL;
        
        while(n){
            quick = quick->next;  
            if(!quick->next && n !=1){
                return newhead->next->next;
            }
            n--;  
        }
        
        while(quick->next){
            quick = quick->next;
            slow = slow->next;
        }
        
        
        if(n == 1)
            slow->next = quick->next;
        else
            slow->next = slow->next->next;      
        return newhead->next;
    }
};

提交时，针对不同的情况，修改了几种判断情况：

  • [1],1：head指向NULL
  • [1,2],2：n=链表长度，删除链表第一个结点，慢指针无需移动，跳过慢指针。
  • [1,2],1：n=1，删除链表最后一个元素，slow->next = quick->next(NULL)
  • [1,2,3,4,5],3：删除链表中间结点，slow->next = slow->next->next;

可以看出，这样思路正确，但是代码不简洁，判断容易出错，需要理清各种情况。

2、简洁思路

将quick、slow指针都指向标记结点newhead，newhead指向第一个结点。quick比slow领先n+1个位置。这样当quick是NULL时，slow->next即需要跳过。该思路整合了上述所有情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *newhead = new ListNode(-1);
        newhead->next = head;
        ListNode *slow = newhead,*quick =newhead;
        for(int i=1;i<=n+1;i++){
            quick = quick->next;
        }
        
        while(quick != NULL){
            quick = quick->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return newhead->next;
    }
};