首页 > 代码库 > leetcode - Remove Nth Node From End of List

leetcode - Remove Nth Node From End of List

2024-07-10 06:33:01   225人阅读

题目：Remove Nth Node From End of List

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.

 

个人思路：

1、设置两个指针，一个快，一个慢，根据给定的n，让快指针先走n步，之后再同时走，直到快指针走到末节点，此时慢指针走到要删除节点的父节点

2、注意一下边界条件即可，链表为空、删除头节点等情况

代码：

 1 #include <stddef.h> 2  3 struct ListNode 4 { 5     int val; 6     ListNode *next; 7     ListNode(int x) : val(x), next(NULL) {}; 8 }; 9 10 class Solution11 {12 public:13     ListNode* removeNthFromEnd(ListNode *head, int n)14     {15         if (!head)16         {17             return NULL;18         }19 20         ListNode *slow = head;21         ListNode *fast = head;22 23         //快指针先走n步24         for (int i = 0; i < n; ++i)25         {26             fast = fast->next;27         }28         //快指针为空，表明要删除的节点为头节点29         if (!fast)30         {31             head = head->next;32             delete slow;33             slow = NULL;34 35             return head;36         }37         //快指针走到最后一个节点时，慢指针走到要删除节点的前一个节点38         while (fast->next)39         {40             slow = slow->next;41             fast = fast->next;42         }43         //删除节点44         ListNode *deleted = slow->next;45         slow->next = deleted->next;46         delete deleted;47         deleted = NULL;48 49         return head;50     }51 };52 53 int main()54 {55     return 0;56 }
View Code

 

网上的文章大部分都是这个思路


联系
我们