O(n) solution in Java


  • 2
    A
    public class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if(head == null){
                return null;
            }
    
            ListNode fast = head;
            ListNode slow = head; 
            for(int i = 0; i < n; i++){
                fast = fast.next;
            }
            if(fast == null){
                head = head.next;
                return head;
            }
            while(fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            ListNode curr = slow.next;
            slow.next = curr.next;
            
            return head; 
        }
    }

  • 0

    You're saying you can remove the last node in O(1). That's not correct.


  • 0
    A

    what do you mean


  • 0
    This post is deleted!

  • 0

    Removing the last node means n=1. You're claiming O(n), i.e., in that case, O(1). Which is wrong. Your first loop indeed is O(n), but your second loop isn't.

    O(n) is impossible.


  • 0
    X

    I think you misunderstand O(n), the author is right. try to understand what is O(n)


  • 0

    @xhansong Hahahahaha, good one. No, you're wrong. Probably making the same mistake as the author (i.e., saying "n" out of habit when referring to the number of elements, not realizing that "n" already has a different meaning here).


  • 0
    X

    However, I think "n" in this problem means the number of elements. Is there a solution of O(n) which you mean?


  • 0

    "However, I think "n" in this problem means the number of elements."

    No it doesn't. As I already told you. And as is clear from the problem. And as is clear from the code.

    "Is there a solution of O(n) which you mean?"

    No idea what you mean.


  • 0
    A

    I think @xhansong asked you about an O(n) solution. You can go check other posted solution, people are all using n as the number of nodes in the list. This is a habit that people use n as the number of items


  • 0

    Well unless they're explicitly redefining n, they're all wrong.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.