LeetCode #19 Remove Nth Node From End of List

Posted on | Post modified | In , , , , , ,

Problem

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

Example

1
2
3
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

Method: Iterative

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return head

        nodes = []

        while head:
            nodes.append(head)
            head = head.next

        if n == len(nodes):
            if n == 1:
                return []
            else:
                return nodes[1]
        else:
            nodes[-n-1].next = nodes[-n].next
            return nodes[0]

Solution2

Method: Iterative

Time Complexity: O(n)

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        def length(head):
            count = 0
            while head:
                count += 1
                head = head.next          
            return count

        def nthNode(head, n):
            ptr = head
            while n > 0:
                ptr = ptr.next
                n -= 1
            return ptr

        count = length(head)
        if count <= 1:
            return []

        if n == count:
            return head.next
        else:
            node = nthNode(head, count - n - 1)
            node.next = node.next.next        
            return head

Solution3[1]

Method:

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
# value shifting
class Solution:
    def removeNthFromEnd(self, head, n):
        def index(node):
            if not node:
                return 0
            i = index(node.next) + 1
            if i > n:
                node.next.val = node.val
            return i
        index(head)
        return head.next

Solution4[1]

Method:

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
# index and remove
class Solution:
    def removeNthFromEnd(self, head, n):
        def remove(head):
            if not head:
                return 0, head
            i, head.next = remove(head.next)
            return i+1, (head, head.next)[i+1 == n]
        return remove(head)[1]

Solution5[1]

Method:

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
# n ahead
class Solution:
    def removeNthFromEnd(self, head, n):
        fast = slow = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

Reference

[1] https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/8802/3-short-Python-solutions