19. Remove Nth Node From End of List

难度: Medium

题目描述

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

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

解题思路

代码实现

解决方案

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        int len = getLength(head);
        if (n > len) {
            return null;
        }
        int realDeleteIndex = len - n;

        ListNode pre = null;
        ListNode headP = head;
        int index = 0;
        while (headP != null) {
            if (index == realDeleteIndex) {
                ListNode next = headP.next;
                headP.next = null;
                if (pre == null) {
                    return next;
                }
                pre.next = next;
                return head;
            }

            pre = headP;
            headP = headP.next;
            index++;

        }

        return head;

    }

    public int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode headP = head;
        int res = 0;
        while (headP != null) {
            res++;
            headP = headP.next;

        }

        return res;
    }
}