LeetCode|Remove Nth Node From End of List

男娘i 2022-07-19 02:23 3阅读 0赞

【问题描述】

Given a linked list, remove the *n*th 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.

【解答】

计算链表长度，要删除元素的位置在length-n处。

两遍遍历：第一遍求链表长度，第二遍进行删除操作。

struct ListNode {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
    };
    ListNode* insert(ListNode* ln,int val)
    {
    	return (ln->next=new ListNode(val));
    }
    
    void print(ListNode* ln)
    {
    	while(ln!=NULL)
    	{
    		cout<<ln->val<<" ";
    		ln=ln->next;
    	}
    }
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
        	int length=0;
        	ListNode* ln=head;
    
        	if(head==NULL || head->next==NULL)
        		return NULL;
        	while(ln!=NULL)
        	{
        		length++;
        		ln=ln->next;
        	}
        	int NthFromHead=length-n;
        	int index=0;
        	ln=head;
        	if(index==NthFromHead)
        	{
        		head=head->next;
        	}
        	else{
        	while(index!=NthFromHead-1)
        	{
        		ln=ln->next;
        		index++;
    
        	}
        	ln->next=ln->next->next;
        	}
    
        	return head;
    
        }
    };
    
    int main() {
    	Solution s;
    	ListNode* ln=new ListNode(1);
    	ListNode* head=ln;
    	for(int i=2;i<3;i++)
    	{
    		ln=insert(ln,i);
    	}
    	int n=2;
    	ListNode* rln=s.removeNthFromEnd(head,n);
    	print(rln);
    	return 0;
    }

【遇到问题】

错误1：输入 \[1\] 1，对于只含有一个元素的单链表不能正确处理，由于访问了其next元素，导致程序崩溃。添加判断语句，如果输入为空或者链表中只有一个元素则直接返回NULL。

错误2：输入\[1,2\] 2，

index!=NthFromHead-1

index表示要删除元素的上一个元素。对于单链表来说，如果要删除元素为第一个元素，此时index==NthFromHead。这时候我们不应该向后寻找，而殷应该直接删除第一个元素。添加添加判断解决，是的head直接指向其next元素。

【改进程序】

采用双指针，两个指针位置相距n-1；当其中一个到达单链表尾部时，另一个指针正好在要删除元素的前一个位置。

class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
        	ListNode* ln1=head;
        	ListNode* ln2=head;
        	if(head==NULL || head->next==NULL)
        		return NULL;
        	for(int i=0;i<n;i++)
        		ln1=ln1->next;
        	if(ln1==NULL)//确定要删除的是首部元素
        		head=head->next;
        	else
        	{
        		while(ln1->next!=NULL)
        		{
        			ln1=ln1->next;
        			ln2=ln2->next;
        		}
        		ln2->next=ln2->next->next;
        	}
        	return head;
    
    
        }
    };

【遇到问题】

while(ln1->next!=NULL)最初错写为while(ln1!=NULL)，导致输入为\[1,2\] 1时不能得到正确答案。

while循环应保证ln2正好指向要删除元素的前一个位置。