Lintcode 166. 链表倒数第n个节点

Lintcode 166. 链表倒数第n个节点

-----------------------------------

最开始的想法是先计算出链表的长度length,然后再从头走 length-n 步即是需要的位置了。

AC代码:

/**
* 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.
*/
ListNode nthToLast(ListNode head, int n) {
int length=0;
ListNode node=head;
while(node!=null){
length++;
node=node.next;
}
for(int i=length-n;i>0;i--){
head=head.next;
}
return head;
}
}

然后神奇的快慢指针出场打脸了...

两个指针间距n(慢指针+n=快指针),当快指针到达尾部的时候慢指针所处的位置就是我们需要的啦。

AC代码:

/**
* 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.
*/
ListNode nthToLast(ListNode head, int n) {
ListNode fast, slow;
fast=slow=head; while(n-->0) fast=fast.next; while(fast!=null){
fast=fast.next;
slow=slow.next;
} return slow;
}
}

题目来源: http://www.lintcode.com/zh-cn/problem/nth-to-last-node-in-list/

上一篇:BZOJ 3211 题解


下一篇:转~~~ DIV+CSS实现三角形提示框