'lintcode 链表倒数第n个节点'

Posted on | In

lintcode 链表倒数第n个节点

每日一练 加油

描述

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

样例

给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1.

思路

第一个反应，先检索出链表的长度Num，然后倒数第n个就是正数第Num-n+1个，就可以解决了，这样要遍历整个链表一次再遍历到第Num-n+1个位置，指针一共移动了 Num-1+Num-n+1-1 = 2*Num - n-1次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /*
     * @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) {
        // write your code here
        ListNode *cur = head;
        int Num = 0;
        while(cur) {
            Num++;
            cur = cur->next;
        }
        cur = head;
        while(Num-n) {
            cur = cur->next;
            Num--;
        }
        return cur;
    }
};

如果使用两个指针 cur和pre，先将pre往后移动n-1次，然后cur和pre一起向后移动，知道pre是最后一个节点，那么cur就是倒数第n个，因为最后一个节点和倒数第n个节点的位置差为n-1。可以计算出，两个指针一共移动了也是2*Num-n-1次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /*
     * @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) {
        // write your code here
        if (!head)
            return NULL;
        ListNode *cur = head,
                 *pre = head;
        int step = n-1;
        while(step) {
            pre = pre->next;
            step--;
        }
        while(pre->next) {
            cur = cur->next;
            pre = pre->next;
        }
        return cur;
    }
};

单从指针的移动次数来讲其实是没有差别的，但是运行之后可以看出下面的代码运行的速度更快一点，个人分析来判断，是因为第一种方法的Num计数 再循环种和指针移动次数一样，而第二种只需要n-1次。

第二种方法中使用两个指针的思想需要记住。

-------------end of filethanks for reading-------------