3112、访问消失节点的最小时间

题目

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

示例：

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

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

说明：给定的 n 保证是有效的。

进阶：

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

分析

• 倒数第n个节点，求出链表长度len，走 len-n步，到达倒数第n个节点。

• 双指针

  • 快指针先走n步，
  • 慢指针开始走，直到快指针走到链表尾部
    • 则慢指针当前指向倒数第n个节点

原理：len = m + n = n + m

• 设总长度 len = m + n
  • 那么总长度也等于 len = n + m
  • 我们结合链表长度固定，让快指针先走n步，满指针走m步后
  • 快指针到达尾部，此时满指针就是指向n的第一个节点。

代码

// 头节点法、一趟遍历
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        
        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        
        for (int i = 0;i < n + 1;i++) {
            q = q->next;
        }
        
        while(q) {
            p = p->next;
            q = q->next;
        }
        
        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;
        
        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        
        return retNode;
    }
};

// 我的方法

ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 异常处理
        if (head == nullptr) return nullptr;

        // 统计节点的总数
        ListNode* p = head;
        ListNode* pre = p;
        int count = 0;
        while (p != nullptr) {
            count++;
            pre = p;
            p = p->next;
        }

        // 特殊情况处理
        if (count < n) return head;
        if (count == n) {
            ListNode* t = head->next;
            delete head;
            return t;

        }
        if (n == 1) return pre;

        // 一般情况，倒数第n个节点，n = 1 || count
        ListNode* q = head;
        cout<<q->val<<" ";
        // 先走n步
        for (int i = 0;i < n; i++) {
            q = q->next;
            cout<<q->val<<" ";
        }
        cout<<endl;
        // 找倒数第n个节点
        p = pre = head;
        while (q != nullptr) {
            pre = p;
            cout<<"q = "<<q->val<<", p = "<<p->val<<" ";
            p = p->next;
            q = q->next;
        }
        cout<<endl;
        // 删除该节点
        ListNode* t = p;
        delete t;
        pre->next = p->next;

        return head;
    }

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

 // way 1 两次遍历，辅助头节点
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 辅助头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        // 统计总数
        ListNode first =  head;
        while(first != null) {
            length++;
            first = first.next;
        }
        
        //问题转换，求顺数第len - n个节点
        length-=n;
        first = dummy;
        while(length > 0) {
            length--;
            first = first.next;
        }
        
        first.next  = first.next.next;
        
        return dummy.next;
    }
}

// way 2,一次遍历，辅助头节点，双指针法
class Solution2 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 辅助头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 都从辅助头节点开始
        ListNode first =  dummy;
        ListNode second = dummy;
        
        // 先走n+1步
        for (int i = 1;i <= n+1;i++) {
            first = first.next;
        }
        
        // 问题转换，求顺数第len - n个节点
        while(first != null) {
            first = first.next;
            second = second.next;
        }
        
        second.next  = second.next.next;
        return dummy.next;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com