leetcode19：删除链表的倒数第N个结点

题目链接

leetcode

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    第一次遍历：
        求出链表长度 L
    第二次遍历：
        倒数第 n 个结点，就是正数第 L - n + 1 个结点。
        为了方便删除操作，添加虚拟头结点，从虚拟头结点开始遍历 L - n + 1 个结点。
        当遍历到第 L - n + 1 个结点时，它下一个结点就是需要删除的结点。

    时间复杂度：O(n)
        其中 n 是链表的长度，对链表进行一次遍历。
    空间复杂度：O(1)
        只使用了固定的额外空间。
*/
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        int length = 0;
        for (ListNode* p = dummy; p; p = p->next) length ++;

        ListNode* p = dummy;
        for (int i = 1; i < length - n; i ++) p = p->next;
        p->next = p->next->next;

        return dummy->next;
    }
};

/*
    双指针，遍历一次
    1.设置两个指针 first 和 second，都指向头结点。
    2. first 指针向后移动 n + 1 个结点
    3. first 和 second 指针同时向后移动，直到 first 指针指向空。
    4. second 指针指向的结点就是需要删除的结点。
    说明如下：
        倒数第 n 个结点，就是第 L - n + 1 个结点。
        first 到达终点时，second 指向第 L - n 个结点，second 指向的下一个结点需要删除。

    时间复杂度：O(n)
        其中 n 是链表的长度，对链表进行一次遍历。
    空间复杂度：O(1)
        仅需要定义常数个指针变量，故空间复杂度为 O(1)。

    参考：https://www.acwing.com/solution/content/67/
*/
class Solution_1 {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        // 查找倒数第 n + 1 个结点
        ListNode *first = dummy, *second = dummy;
        for (int i = 0; i <= n; i ++) {
            first = first->next;
        }
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }
        // 删除第 n 个结点
        second->next = second->next->next;

        return dummy->next;
    }
};

/*
    思路同上
*/
class Solution_2 {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        // 查找倒数第 n + 1 个结点
        ListNode* p = findNodeFromEnd(dummy, n + 1);
        // 删除第 n 个结点
        p->next = p->next->next;

        return dummy->next;
    }

    ListNode* findNodeFromEnd(ListNode* head, int k) {
        ListNode* p1 = head;
        // p1 走 k 步
        for (int i = 0; i < k; i ++) {
            p1 = p1->next;
        }
        ListNode* p2 = head;
        // p1, p2 同时走 n - k 步
        while (p1 != nullptr) {
            p2 = p2->next;
            p1 = p1->next;
        }
        // p2 指向第 n - k 个结点
        return p2;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5};
    int n = 2;

    // 创建链表
    ListNode* head = createList(nums);

    // 删除操作
    ListNode* result = solution.removeNthFromEnd(head, n);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    deleteList(result);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表结点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    设置一个哑结点连接到链表头部，
    快指针先向前移动 n 步，接着同时移动快指针和慢指针，
    当快指针到达链表末尾时，慢指针正好停在倒数第 n 个结点的前一个结点，此时进行删除操作。
        
    时间复杂度：O(n)
        其中 n 是链表的长度，对链表进行一次遍历。
    空间复杂度：O(1)
        只使用了固定的额外空间。
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy

    // 查找倒数第 n + 1 个结点
    for i := 0; i <= n; i ++ {
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    // 删除倒数第 n 个结点
    slow.Next = slow.Next.Next

    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        head     []int
        n        int
        expected []int
    }{
        {
            head:     []int{1,2,3,4,5},
            n:        2,
            expected: []int{1,2,3,5},
        },
        {
            head:     []int{1},
            n:        1,
            expected: []int{},
        },
        {
            head:     []int{1,2},
            n:        1,
            expected: []int{1},
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.head)
        fmt.Printf("Test Case %d, Input: head = %v\n", i+1, printLinkedList(head))
        result := removeNthFromEnd(head, tc.n)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}