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.
Naive Way: Keep two pointers, let the second pointer move n step first. Then the gap between two pointers is n. Keep moving both pointers forward at same speed until second one reach the end. Then reconnect.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fake = new ListNode(0);
fake.next = head;
ListNode first = fake, second = fake;
// forward second by n
while(n-->0 && second.next!=null) second = second.next;
// edge case, length of linkedlist< n
if(n > 0){return head;}
// forward first and second till second reach the end
while(second.next!=null){
first = first.next;
second = second.next;
}
ListNode temp = first.next.next;
first.next = temp;
return fake.next;
}
}
No comments:
Post a Comment