Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

难度：medium

Solution: Two Pointers

这个问题的关键是用两个指针：第一个指针用来定位被删除元素之前的那个元素的位置，但是这就需要第二个指针来确定是否第一个指针已经指向对应的位置。让两个指针的位置相差n个，当第二个指针指向最后一个元素的时候，第一个指针就指向的对应的位置。（如果让两个指针的位置相差n + 1个，当第二个指针指向null时，第一个指针才指向对应的位置。）另外对于所有linked list的删除添加我们一般都需要一个dummy head来简化操作。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode first = dummyHead, second = dummyHead;
        for(int i = 0; i <= n; ++i) {
            second = second.next;
        }
        while(second != null) {
            first = first.next;
            second = second.next;
        }
        first.next = first.next.next;
        return dummyHead.next;
    }
}

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

难度：medium

Solution: Two Pointers

这个问题不仅需要考虑到k大于list的长度的情况，还要考虑k特别大时导致的超时。所以我们需要先找到k和list长度的关系，使得k小于list的长度。当有长度之后我们可以直接从开始找到length - k的位置，然后再重新构造list。另外一个技巧是，当找到最后一个元素之后，先构造一个circular list，然后rotate，然后break这个circular list。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) {
            return head;
        }
        int listLength = 1;
        ListNode ptr = head;
        while(ptr.next != null) {
            ++listLength;
            ptr = ptr.next;
        }
        ptr.next = head;

        k %= listLength;
        for(int i = 0; i < listLength - k; ++i) {
            ptr = ptr.next;
        }
        head = ptr.next;
        ptr.next = null;
        return head;
    }
}