Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 LeetCode link: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm topic is linked list manipulation.

A common technique used to manipulate linked lists is to add a dummy node whose next pointer points to the head of the list. In this way, we do not need to make special judgments about the head node.

  • According to the description of the problem, first traverse the linked list once to find the length of the list, and then traverse the list a second time to find the target node and point to the next node. The implementation code is as follows:

Through the code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        int listNodeLength = 0;
        while(head ! =null) {
            head = head.next;
            listNodeLength++;
        }

        ListNode cur = dummy;
        for (int i = 1; i < listNodeLength - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;

        returndummy.next; }}Copy the code

conclusion

  • The time complexity of the above algorithm is O(n) and the space complexity is O(1).
  • Adhere to the algorithm of the day, come on!