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春弥，再倒推倒數(shù)第n個(gè)節(jié)點(diǎn)刪除
- 雙指針
這種題畫圖比較好做
- 技巧:
- dummy node指向head
- 雙指針
Solution
第一種方法AC解：
需要一個(gè)dummy指針呛哟，一個(gè)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)
