Description
Given a linked list, remove the nth
node from the end of list and return its head.
For 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.Try to do this in one pass.
Analysis
有两种方法：
- 先算链表的长度L，再倒推倒数第n个节点删除
- 双指针
这种题画图比较好做
- 技巧:
- dummy node指向head
- 双指针
Solution
第一种方法AC解：
需要一个dummy指针，一个first指针，详见代码
ListNode removeNthFromEnd(ListNode head, int n) {
// write your code here
int length = 0;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = head; // need a first pointer
while (first != null) {
first = first.next;
length++;
}
first = dummy;
int i = 0;
while (i < length - n ) {
first = first.next;
i++;
}
first.next = first.next.next;
return dummy.next;
}
Time Complexity: O(L)
Space Complexity: O(1)
第二种做法AC解：
ListNode removeNthFromEnd(ListNode head, int n) {
// write your code here
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
int i = 0;
while (i < n + 1) {
first = first.next;
i++;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
Time Complexity: O(L)
Space Complexity: O(1)
