This is the seventh day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Given a linked list, delete the NTH last node of the list and return the first node of the list.

Their thinking

The problem shows that its final results returned after the head of the list is to remove node, if according to the conventional way of thinking, you will need to determine whether the current delete nodes as the head node, and makes two judgment according to the yes and no, code logic can appear more chaos, can add a head node here, will be given as the head of the newly created node in the list next, The logic for subsequent deletion is relatively simple. After deleting, return next of the head node. The code is as follows:

public static ListNode removeNthFromEnd(ListNode head, int n) {
        int len =0;
        ListNode cur = head;
        ListNode headpoint = new ListNode(0, head);
        ListNode temp = headpoint;
        while(cur! =null){
            len++;
            cur = cur.next;
        }
        for(int i=1; i<len-n+1; i++){ temp = temp.next; } temp.next = temp.next.next;return headpoint.next;
    }
Copy the code

In this way, the previous node of the deleted node is obtained, and then the final result can be obtained according to the simple linked list deletion logic. Its time complexity is O(N)O(N)O(N) O(1)O(1)O(1) O(1). LeetCode’s results show more than 100%. However, this problem is the result of scanning the linked list twice. The advanced requirement of the question is whether the result can be obtained only once, and how to achieve it?

Advanced solution (scan the list only once)

Another idea is to still create an empty head nodes in advance, after the next point to the head, traversing the list in turn, will list elements into the stack (using the stack after the advanced features, list the reciprocal of the NTH node as the first n the stack elements), after going to delete the elements of the stack elements can get stack, according to the character of the linked list to delete a result can be simple, The code is as follows:

public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode headpoint = new ListNode(0, head);
        ListNode cur = headpoint;
        Stack<ListNode> s = new Stack<>();
        while(cur! =null){
            s.push(cur);
            cur = cur.next;
        }
        for(int i=0; i<n; i++){ s.pop(); } ListNode peak = s.peek(); peak.next = peak.next.next;return headpoint.next;
    }
Copy the code

The time complexity of this method is O(N)O(N)O(N) O(N)O(N)O(N) O(N).

How fast a pointer

A more subtle approach is to use double pointer to the solution, the NTH node from bottom to delete list, only need to first set the speed pointer, make speed pointer distance interval for n, moves the pointer speed, respectively, after making fast pointer is empty, slow pointer to stay after removing elements of the previous node, according to the list to delete rules can be perfect to delete, The code is as follows:

public static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode headpoint = new ListNode(0, head);
        ListNode low = headpoint;
        ListNode fast = head;
        for(int i=0; i<n; i++){ fast = fast.next; }while(fast! =null){
            fast = fast.next;
            low = low.next;
        }
        low.next = low.next.next;
        return headpoint.next;
    }
Copy the code

The time complexity of the above method is still O(N)O(N)O(N), because only constant variables are used, so the space complexity is O(1)O(1)O(1).