leetcode:19. Remove Nth Node From End of List

悠悠 2024-04-17 22:06 12阅读 0赞

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

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.

Follow up:

Could you do this in one pass?

题意：  
从链表摘除倒数第n个元素。一次性通过。

坑的测试用例：  
链表：1->2->3->4->5,n=1,5,4  
链表：1，n=1

代码：

class Solution { 
    public:
    	ListNode* removeNthFromEnd(ListNode* head, int n) { 
    		vector<ListNode *> node_p;
    		ListNode *tmp = head;
    		while (tmp)
    		{ 
    			node_p.push_back(tmp);
    			tmp = tmp->next;
    		}
    		int len = node_p.size();
    		if (n <= 0)
    		{ 
    			return head;
    		}
    		if (n > len)
    		{ 
    			return head;
    		}
    		if (n == 1 && len == 1)
    		{ 
    			head->next = NULL;
    			head = NULL;
    			return head;
    		}
    		if (n ==1)
    		{ 
    			node_p[len - 2]->next = NULL;
    			//free(node_p[len - 1]);
    			return head;
    		}
    		else if(n == len)
    			//head
    		{ 
    			node_p[0]->next = NULL;
    			//free(node_p[0]);
    			return node_p[1];
    		}
    		else
    		{ 
    			int index = len - n;
    			node_p[index - 1]->next = node_p[index]->next;
    			//free(node_p[index]);
    			return head;
    		}
    
    	}
    };

结果：  
Runtime: 4 ms, faster than 85.84% of C++ online submissions for Remove Nth Node From End of List.  
Memory Usage: 8.6 MB, less than 71.05% of C++ online submissions for Remove Nth Node From End of List.