程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Remove Nth Node From End of List

leetcode筆記:Remove Nth Node From End of List

編輯:關於C++

一. 題目描述

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.

二. 題目分析

給出一個鏈表, n是指刪除倒數n個節點。這裡的提示n的值默認是合法的。不過其實對輸入的n進行異常判斷也只需要幾句語句。

使用兩個指針,即快/慢指針的概念,其中一個指針先走n步,然後慢指針走,等到快指針走到結尾時,那麼慢指針走到了需要刪除的節點的前一個位置

這道題主要難點是考慮邊界問題,以及特殊情況(要刪除的是頭節點),如輸入1->2->3->4n=4,那麼需要刪除1,此時只需將頭指針head = head->next就可以了。

三. 示例代碼

#include 

struct ListNode
{
    int value;
    ListNode* next;
    ListNode(int x): value(x), next(NULL){};
};

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        if (head == NULL)
            return NULL;
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *temp = head;
        for (int i = 0; i < n ; i++)
        {
            fast = fast->next;
            if (fast)
                continue;
            else break;
        }
        while (fast)
        {
            fast = fast->next;
            temp = slow;
            slow = slow->next;
        }
        if (slow == head)
        {
            head = head->next;
            return head;
        }
        temp->next = slow->next;
        delete slow;
        return head;
    }
};

結果:

這裡寫圖片描述

這裡寫圖片描述

這裡寫圖片描述編程中經常會遇到邊界問題,不小心的錯誤很容易造成程序奔潰,關於指針和鏈表的使用技巧還需要進一步的學習。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved