Remove Nth Node From End of List

Question

  1. Given a linked list, remove the nth node from the end of list and return its head.
  3. Note
  4. The minimum number of nodes in list is n.
  6. Example
  7. Given linked list: 1->2->3->4->5->null, and n = 2.
  9. After removing the second node from the end, the linked list becomes 1->2->3->5->null.
  11. Challenge
  12. O(n) time

题解

简单题，
使用快慢指针解决此题，需要注意最后删除的是否为头节点。让快指针先走n步，直至快指针走到终点，找到需要删除节点之前的一个节点，改变node->next域即可。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @param n: An integer.
  18.      * @return: The head of linked list.
  19.      */
  20.     ListNode *removeNthFromEnd(ListNode *head, int n) {
  21.         if (NULL == head || n < 0) {
  22.             return NULL;
  23.         }
  25.         ListNode *preN = head;
  26.         ListNode *tail = head;
  27.         // slow fast pointer
  28.         int index = 0;
  29.         while (index < n) {
  30.             if (NULL == tail) {
  31.                 return NULL;
  32.             }
  33.             tail = tail->next;
  34.             ++index;
  35.         }
  37.         if (NULL == tail) {
  38.             return head->next;
  39.         }
  41.         while (tail->next) {
  42.             tail = tail->next;
  43.             preN = preN->next;
  44.         }
  45.         preN->next = preN->next->next;
  47.         return head;
  48.     }
  49. };

以上代码单独判断了是否需要删除头节点的情况，在遇到头节点不确定的情况下，引入dummy节点将会使代码更加优雅，改进的代码如下。

C++ dummy node

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @param n: An integer.
  18.      * @return: The head of linked list.
  19.      */
  20.     ListNode *removeNthFromEnd(ListNode *head, int n) {
  21.         if (NULL == head || n < 1) {
  22.             return head;
  23.         }
  25.         ListNode dummy(0);
  26.         dummy.next = head;
  27.         ListNode *preDel = dummy;
  29.         for (int i = 0; i != n; ++i) {
  30.             if (NULL == head) {
  31.                 return NULL;
  32.             }
  33.             head = head->next;
  34.         }
  36.         while (head) {
  37.             head = head->next;
  38.             preDel = preDel->next;
  39.         }
  40.         preDel->next = preDel->next->next;
  42.         return dummy.next;
  43.     }
  44. };

源码分析

引入dummy节点后画个图分析下就能确定head和preDel的转移关系了。