leetcode 19. Remove Nth Node From End of List 双指针 + 移动窗口

秒速五厘米 2022-06-09 07:59 109阅读 0赞

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

For example,

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.  
Try to do this in one pass.

题意很简单，就是删除倒数的第n个元素，不过题目要求一次遍历实现。

这个问题的最直接的想法就是两次遍历，首先先遍历一次得到len，然后从正面遍历到len+1-k个元素，并删除。

其实使用栈也是不错的做法

不过题目要求是一次遍历，有什么解决办法呢? 看了网上的解决办法，于是乎才明白可以使用长度为**n+1的子链表来解决，这个类似移动窗口算法**。需要注意的是：使用**n+1的子链表**就是n个间隔n+1个元素，这样是为了便于删除元素；同时要注意处**理删除元素就是head结点的特殊情况**的处理。

代码如下：

/*class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }*/
    
    /*
     * 题目说保证n是有效的，这个意思就是说n<len
     * 同时题目要求一次遍历解决问题
     * 
     * 本题的思想就是利用一个长度为n+1的子链表，，有点类似移动窗口，
     * 通过移动子链表到最后一个结点
     * 从而来确定导数第n个元素是谁，注意这里使用n+1的子链表就是为了方便删除元素，
     * 这个很容易理解
     * 
     * */
    public class Solution 
    {
        /*
         * 这个是两次遍历的解决办法
         * */
         public ListNode removeNthFromEnd(ListNode head, int n)
         {
             if(head==null || n<=0)
                 return head;
    
             ListNode iter=head;
             int count=0;
             while(iter!=null)
             {
                 iter=iter.next;
                 count++;
             }
    
             if(count==n)
                 head=head.next;
             else 
             {
                 int target=count+1-n;
                 iter=head;
                 ListNode fa=head;
                 for(int i=1;i<=target;i++)
                 {
                     if(i==target)
                     {
                         fa.next=iter.next;
                         break;
                     }else 
                     {
                         fa=iter;
                         iter=iter.next;
                     }
                 }
    
             }       
             return head;
         }
    
         /*
          * 使用长度为n+1的子链表实现，有点类似移动窗口
          * */
         public ListNode removeNthFromEnd11(ListNode head, int n)
         {
             if(head==null || n<=0)
                 return head;
    
             ListNode start=head,end=head;
    
            /*
             * 因为n是有效的，所以这个循环不会报错，最多end为null走到了最后
             * 这里是循环次数为n的for循环，表示的子链表的间隔是n，也就是说元素是n+1个
             * */
             for(int i=0;i<n;i++)
                 end=end.next;
    
            if(end==null)
                head=head.next;
            else 
            {
                while(end.next!=null)
                {
                    start=start.next;
                    end=end.next;
                }
                //start 到 end 是n个间隔，就是有n+1个点，所以start.next才是我们要删除的结点
                start.next=start.next.next;
            }
             return head;
         }
    }

下面是C++的一次遍历的做法，就是一个移动窗口问题。

代码如下：

#include <iostream>
    #include<stdio.h>
    using namespace std;
    
    /*
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) 
        {
            if (head == NULL || n <= 0)
                return head;
    
            ListNode* start = head;
            ListNode* end = head;
    
            for (int i = 0; i < n; i++)
                end = end->next;
    
            if (end == NULL)
                head = head->next;
            else
            {
                while (end->next != NULL)
                {
                    start = start->next;
                    end = end->next;
                }
                start->next = start->next->next;
            }
            return head;
        }
    };