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

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?

代码

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;
}
}