C语言重构【28】删除链表的倒数第N个节点

男娘i 2022-12-09 14:54 82阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

实现 strStr() 函数。
    
    给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
    
    示例 1:
    
    输入: haystack = "hello", needle = "ll"
    输出: 2
    示例 2:
    
    输入: haystack = "aaaaa", needle = "bba"
    输出: -1
    说明:
    
    当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
    
    对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

#### 方案： ####

*  双指针法

#include <iostream>
    #include <string>
    #include <stack>
    
    using namespace ::std;
    
    struct ListNode
    { 
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) { }
    };
    
    class Solution
    { 
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n)
        { 
    
            int t = 0;
            ListNode *left = head;
            ListNode *right = head;
            while (right->next != NULL && t++ < n)
                right = right->next;
            if (t < n)
                return left->next;
            while (right->next != NULL)
            { 
                right = right->next;
                left = left->next;
            }
            left->next = left->next->next;
            return head;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode