19.Remove-Nth-Node-From-End-of-List

19. Remove Nth Node From End of List

题目地址

https://leetcode.com/problems/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?

代码

Approach #1 Two pass

/**
 * 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) {
        ListNode dummy = new LstNode(0);
    dummy.next = head;
    int length = 0;
    listNode first = head;
    while (first != null) {
      length++;
      first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
      length--;
      first = first.next;
    }
    first.next = first.next.next; // 只能覆盖 second.next
    return dumy.next;
  }
}

Approach #2 One pass

class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode  first = dummy;
    ListNode second = dummy;

    for (int i = 1; i <= n + 1; i++) {
      first = frist.next;
    }

    while (first != null) {
      first = first.next;
      second = second.next;
    }
    second.next = second.next.next; // 只能覆盖 second.next
    return dummy.next;
  }
}