19. Remove Nth Node From End of List

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

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.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution

(1) Java

Two pointer, the distance is n

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode forward = head;
        int i = n;
        while (i > 0) {
            forward = forward.next;
            i--;
            if (i == 0 && forward == null) {
                break;
            } else if (forward == null) {
                return head;
            }           
        }
        while (forward != null) {
            forward = forward.next;
            prev = prev.next;
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
}

(2) Python

Using recursive seems more clear, without dummy node

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return head
        moveNode = head
        def helper(node):
            if not node:
                return 0
            idx = helper(node.next)+1
            if idx == n+1:
                node.next = node.next.next
            return idx
        idx = helper(moveNode)
        if idx <= n:
            return head.next
        return head

(3) Scala

/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 *   var x: Int = _x
 * }
 */
object Solution {
    def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
        if (head == null) {
            return head
        }
        val idx = helper(head, n)
        if (idx <= n) {
            return head.next
        }
        return head
    }

    def helper(node: ListNode, n:Int): Int = {
        if (node == null) {
            return 0
        }
        val idx = helper(node.next, n)+1
        if (idx == n+1) {
            node.next = node.next.next
        }
        return idx
    }
}

Iterative version

object Solution {
    def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
        head match {
            case null => return head
            case node: ListNode => {
                var prev: ListNode = null
                var slow: ListNode = head
                var fast: ListNode = head
                for (i<-0 until n if fast != null) {
                    fast = fast.next
                }
                if (fast == null) {
                    return slow.next
                }
                while (fast != null) {
                    prev = slow
                    slow = slow.next
                    fast = fast.next
                }
                prev.next = prev.next.next
                head
            }
        }
    }
}