一、需求

找到单链表的倒数第n个节点，保证链表中节点的最少数量为n。

二、解题方案一

两个指针，先让快指针走n步， 然后一起走，快指针到头的时候，慢指针就是倒数第n个。

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         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) {
        if(head == null || n < 1){
            return null;
        }

        ListNode p1 = head;
        ListNode p2 = head;

        for (int i = 0 ; i < n; i++){
            // 总数量4小于倒数个数5
            if (p2 == null){
                return null;
            }
            // p2 先走倒数的n步
            p2 = p2.next;
        }

        while(p2 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

三、解题方案二

创建新的ListNode对象，通过对原ListNode对象的遍历，让新ListNode的next指向原ListNode的父节点，最后取新ListNode的第N条数据即可。

(adsbygoogle = window.adsbygoogle || []).push({});