链表倒数第n个节点

题意

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

样例

给出链表 3->2->1->5->nulln = 2,返回倒数第二个节点的值 1

思路1

一个简单的思路就是先将链表进行反转,然后在反转后的链表中,顺着找第 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
/**
* 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 node = null;

while (head != null) {
ListNode temp = head.next;
head.next = node;
node = head;
head = temp;
}

for (int i = 1; i < n; i++) {
node = node.next;
}

return node;
}
}

思路2

考虑一下思路1会出现的问题:当链表很长时,效率会大大降低。例如对于 100 个元素的链表,查找倒数第 100 个,那么就等于将链表遍历了 2 次,效率很低。

改进思路:

  1. 设 2 个指针 p1, p2
  2. 先让指针 p2 指向顺数第 n 个元素,p1 指向原链表的头指针。
  3. 然后 p1 和 p2 一起向后移动,直到 p2 指向 NULL,此时 p1 就会指向倒数第 n 个元素上。

代码实现2

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
/**
* 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) {
if (head == null || n < 1) {
return null;
}

ListNode p1 = head;
ListNode p2 = head;
for (int j = 0; j < n - 1; ++j) {
if (p2 == null) {
return null;
}
p2 = p2.next;
}
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}

原题地址

LintCode:链表倒数第n个节点

坚持原创技术分享,您的支持将鼓励我继续创作!