Remove Node From End of List (in Python)

Problem

Given a linked list, remove the n-th node from the end of list and return its head.

Note:

Given n will always be valid.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

Approach 1 : Two pass algorithm

Remove the (L-n+1)th node from the beginning in the list, where L is the list length.

•while문을 이용해서 linked list의 길이(length)를 구함.

•현재 제거하고자하는 노드인 (length-n)번째 노드의 이전 노드를 구함.

- first 변수에 head가 아닌 dummy 노드를 저장.

•first 노드의 next를 다음 노드의 next 로 변경.

    def removeNthFromEnd(head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
 
        length = 0
 
        dummy = ListNode(0)
        dummy.next = head
 
        first = head
 
        while first != None :
            length += 1
            first = first.next
 
        length -= n
        first = dummy
 
        while length > 0 :
            first = first.next
            length -= 1
 
        first.next = first.next.next 
        return dummy.next

Complexity Analysis

•Time complexity : \(O(L)\). First to calculate list length L and second to find the (L-n)th node. There are \(2L-n\) operations and time complexity is \(O(L)\). 

•Space complexity : \(O(1)\). We only used constant extra space.

---

Approach 2: One pass algorithm

Figure 2. Remove the nth element from end of a list.

    def removeNthFromEnd(head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
 
        right = head
 
        for i in range(n) :
            right = right.next
 
        if not right :
            return head.next
 
        left = head
 
        while right.next :
            right = right.next
            left = left.next
        
        left.next = left.next.next
 
        return head

Complexity Analysis

•Time complexity : \(O(L)\). The algorithm makes one traversal of the list of L nodes.Therefore time complexity is \(O(L)\).

•Space complexity : \(O(1)\). We only used constant extra space.

Source

https://leetcode.com/problems/remove-nth-node-from-end-of-list/