Difficulty: Medium
More:【目录】LeetCode Java实现
Description
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
Given a linked list, remove the n-th node from the end of list and return its head.
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.
Follow up:
Could you do this in one pass?
Intuition
Using a dummyHead.
Solution
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode n0 = head;
ListNode n1 = head;
ListNode pre = dummy;
for(int i=0; i<n-1; i++)
n1=n1.next;
while(n1.next!=null){
n0=n0.next;
n1=n1.next;
pre=pre.next;
}
pre.next = n0.next;
return dummy.next; //not head
}
Complexity
Time complexity : O(n)
Space complexity : O(1)
More:【目录】LeetCode Java实现