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.
Understand the problem:Given n will always be valid.
Try to do this in one pass.
This is a classical two-pointer problem of linked list. One thing needs to handle is deleting the head node.
Solution:
/** * 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) { if (head == null || head.next == null) return null; ListNode slow = head; ListNode fast = head; // move fast pointer n steps ahead of slow for (int i = 0; i < n; i++) { fast = fast.next; } // move slow and fast pointer one step a time while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next; } // delete the node if (fast == null) { head = head.next; } else { slow.next = slow.next.next; } return head; } }
Summary:
This is an easy question. However, when deal with linked list problem, make sure you cover all the corner cases.
No comments:
Post a Comment