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
給定一個(gè)鏈表，移除從鏈表末尾起的第n個(gè)節(jié)點(diǎn)佛寿，并返回鏈表head
方法一
算法分析
- 首先需要一個(gè)dummy節(jié)點(diǎn)，指向鏈表head位置，主要是為了在鏈表長(zhǎng)度為1時(shí)簡(jiǎn)化代碼隙券。
- 要?jiǎng)h除的節(jié)點(diǎn)在
L-n+1位置（L為鏈表長(zhǎng)度）。 - 找到第
L-n個(gè)節(jié)點(diǎn)竞惋，指向L-n+2個(gè)節(jié)點(diǎn)燎潮。
答案
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = head;
int length = 0;//鏈表長(zhǎng)度
while (current != null) {
length ++;//尋找鏈表長(zhǎng)度
current = current.next;
}
length = length - n;//到要被刪除位置的鏈表節(jié)點(diǎn)的前一個(gè)
current = dummy;
while (length > 0) {
length --;
current = current.next;
}
current.next = current.next.next;//將被刪除的節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)指向被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
return dummy.next;
}
}
方法二
算法分析
- first、second兩個(gè)節(jié)點(diǎn)指向head
- 移動(dòng)first節(jié)點(diǎn)到與second相差n個(gè)節(jié)點(diǎn)的位置
- 同時(shí)移動(dòng)first憨闰、second直到first為null
- 此時(shí)second的下一個(gè)節(jié)點(diǎn)是為要?jiǎng)h除的節(jié)點(diǎn)
答案
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
ListNode first = dummy;
ListNode second = dummy;
dummy.next = head;
for (int i = 1; i <= n + 1; i++) {
first = first.next;//將first移到與second相差n個(gè)節(jié)點(diǎn)
}
while (first != null) {//first和second同時(shí)移動(dòng)状蜗，直到first到最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
