Monday, March 3, 2014

Remove Nth Node From End of List

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.
Code in Java:
public class Rmove_Nth_Node_From_End_of_List {
 //Definition for singly-linked list.
  public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
  }
  public ListNode removeNthFromEnd(ListNode head, int n) {
    /*
     * 1. two start points: head and prev
     * 2. Node n2 move N steps first
     * 3. then n1, n2, head move (L-N) steps together
     * 4. return head.next
     */
    ListNode prev, n1, n2;
    prev = new ListNode(0);
    prev.next = head;
    head = prev;
    n1 = head.next;
    n2 = head.next;
    while (n2 != null && n > 0) {
      n2 = n2.next;
      n--;
    }
    /*
     * Runtime Error Message: Line 28: java.lang.NullPointerException
     * Last executed input: {1}, 1
     */
    if (n > 0) {return n1;}
    while (n2 != null) {
      n2 = n2.next;
      n1 = n1.next;
      prev = prev.next;
    }
    prev.next = n1.next;
    return head.next;
  }
}

The same thought can deal with the question "Rotated List".

No comments:

Post a Comment