LintCode之链表倒数第n个节点

题目描述：

我的代码：

 /**

  * Definition for ListNode.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int val) {

  *         this.val = val;

  *         this.next = null;

  *     }

  * }

  */

 public class Solution {

     /*

      * @param head: The first node of linked list.

      * @param n: An integer

      * @return: Nth to last node of a singly linked list.

      */

     public ListNode nthToLast(ListNode head, int n) {

         // write your code here

         if(head == null) {

             return null;

         }

         ListNode h = new ListNode(-1);

         //倒置单链表

         while(head != null) {

             ListNode node = new ListNode(head.val);

             if(h.next == null) {

                 h.next = node;

             }else {

                 node.next = h.next;

                 h.next = node;

             }

             if(head.next != null) {

                 head = head.next;

             }else {

                 head = null;

             }

         }

         h = h.next;

         //取得倒置后的单链表的第n个节点，这个节点就是原链表的倒数第n个节点

         for(int i=1; i<n; i++) {

             h = h.next;

         }

         ListNode node = new ListNode(h.val);

         return node;

     }

 }

总结：因为这是单链表，无法像双链表一样轻松的获得一个节点的前一个节点，所以，我就把这个单链表倒置，倒置后的单链表的第n个节点就是倒置前的单链表的倒数第n个节点，这样就能通过遍历获得倒数第n个节点了。