題目
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.
了解
删除單向連結清單倒數第n個元素
解決
快慢指針,找到倒數第n+1個元素,注意删除的是頭指針的情況,以及隻有一個節點的情況
增加假頭結點
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fakeHead = new ListNode(0);
fakeHead.next = head;
ListNode slow = fakeHead;
ListNode fast = fakeHead;
while(true){
while(n-->0 && fast.next!=null){
fast=fast.next;
}
if(fast.next==null){
break;
}
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return fakeHead.next;
}
}
頭結點單獨處理
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode faster = head;
ListNode slower = head;
for (int i = 0; i < n; i++) {
faster = faster.next;
}
if (faster == null) {
head = head.next;
return head;
}
while (faster.next != null) {
slower = slower.next;
faster = faster.next;
}
slower.next = slower.next.next;
return head;
}
}