LeetCode

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

nkul · 9月6日 · 2020年 45次已读

所有需要对头结点操作的链表最好添加虚拟头结点,这样对头结点的操作就和其他节点一致!

两趟扫描,第一趟算出链表长度l,删除倒数第n个节点,需要找到倒数第n+1个节点,即正数第(l-n)个.

第二趟扫描将指针指向第l-n个节点,修改next指向即可!

/**
 * 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 k) {
        auto dummy = new ListNode(-1),tail = dummy;;
        dummy->next = head;
        int n=0;
        for(auto p=dummy;p;p=p->next)n++;
        
        for(auto i=0; i < n-k-1;i++){
            tail = tail->next;
        }
        tail->next = tail->next->next;
        return dummy->next;
    }
};

关于进阶做法中的一趟扫描,也即快慢指针,实际上时间复杂度一样!因为两者指针路径都是总长l+l-n

/**
 * 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 *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *fast = dummy;
        ListNode *slow = dummy;
        for(int i=0; i < n ; i++){
            fast = fast->next;
        }
        cout<val;
        while(fast->next!=NULL){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
        
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!