剑指Offer_14

发表于 | 分类于

题目

输入一个链表，输出该链表中倒数第k个结点。

解题思路

解法一：

两趟遍历，第一趟记录链表的总长度n，第二趟跑n-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
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
		if(head == null || k <= 0){
            return null;
        }
        
        int cntNode = 0;
        ListNode p = head;
        while(p != null){
            p = p.next;
            ++cntNode;
        }
        if(cntNode < k){
            return null;
        }
        int i = cntNode - k;
        while(i-- != 0){
            head = head.next;
        }
        return head;
    }
}

解法二：

利用快慢双指针， 当快指针到达k位置时，慢指针开始启动，一旦快指针到达终点(指向null)时，慢指针到达倒数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
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
		if(head == null || k <= 0){
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        
        for(int i = 1; i < k; ++i){
        	//如果指针还没到达k的位置就指向了null
        	//那么k的长度超过链表的长度返回null
            if(fast.next != null){
                fast = fast.next;
            }
            else{
                return null;
            }
        }
        //fast一直跑直到链表尾部的下一节点 null
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}