22:链表中倒数第k个结点

发表于 | 分类于

题目22：链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点。

举例说明

例如一个链表有6 个结点，从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。

思路

为了实现只遍历链表一次就能找到倒数第k 个结点，我们可以定义两
个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1 ， 当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k 个结点。

代码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
public class _22 {
	private static class ListNode {
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}
	}

	public static ListNode findKthToTail(ListNode head, int k) {
		if (k < 1 || head == null) {//k=0也不可以，会导致 k-1=0xFFFFFFFF
			return null;
		}
		ListNode cur = head;
		// 倒数第k个结点与倒数第一个结点相隔k-1个位置
		// 所以，让 cur 先走k-1个位置
		for (int i = 1; i < k; i++) {
			if (cur.next != null) {
				cur = cur.next;
			}else {// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
				return null;
			}
		}
		// cur 先走了k-1步，然后 cur 和 head 一起走，
		// 当cur走到最后一个结点即，cur.next=null时，head就是倒数第k个结点
		while (cur.next != null) {
			head = head.next;
			cur = cur.next;
		}
		return head;
	}

	public static void main(String[] args) {
		// 10 -> 20 -> 30 -> 40 -> 50 -> 60
		ListNode n1 = new ListNode(10);
		ListNode n2 = new ListNode(20);
		ListNode n3 = new ListNode(30);
		ListNode n4 = new ListNode(40);
		ListNode n5 = new ListNode(50);
		ListNode n6 = new ListNode(60);
		n1.next=n2;
		n2.next=n3;
		n3.next=n4;
		n4.next=n5;
		n5.next=n6;
		System.out.println("倒数第1个节点的值是："+findKthToTail(n1, 1).value); 
		System.out.println("倒数第3个节点的值是："+findKthToTail(n1, 3).value);
		System.out.println("倒数第6个节点的值是："+findKthToTail(n1, 6).value);
	}
}

输出：

1
2
3
倒数第1个节点的值是：60
倒数第3个节点的值是：40
倒数第6个节点的值是：10
> >