牛客网在线编程专题《剑指offer-面试题15》链表中倒数第k个节点

题目链接：

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

解题思路：

（1）方法一：两次遍历链表

统计出链表中总共有多少个元素，然后找到第K个元素的位置，最后从链表的头部开始遍历到第k个元素的位置。

已经AC的代码：


public class findKthNode {
	
	class ListNode{
		int val;
		ListNode next = null;
		
		public ListNode(int data) {
			this.val = data;
		}
	}
	
	public ListNode head;
	
	public void createLinkedList(int data) {
		if(head == null) {
			head = new ListNode(data);
		}else {
			ListNode node = new ListNode(data);
			node.next = head;
			head = node;
		}
	}
	
    public ListNode FindKthToTail(ListNode head,int k) {
    	int count = 1;
    	ListNode node = head;
    	if(head == null) {
    		return null;
    	}
    	while(node.next != null) {
    		count++;
    		node = node.next;
    	}
    	if(k > count) {
    		return null;
    	}
    	node = head;
    	for(int i=0; i<count-k; i++) {
    		node = node.next;
    	}
    	return node;
    }

	public static void main(String[] args) {
		findKthNode list = new findKthNode();
		for(int i=0; i<10; i++) {
			list.createLinkedList(i);
		}
		System.out.println(list.FindKthToTail(list.head, 10).val);
	}

}

上面方法的缺点：

对于上面的方法，我们需要遍历链表两次，第一次统计出链表中节点的个数，第二次就能找到倒数第k个节点。但是当我们把这个思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次。

（2）方法二：遍历一次链表

思路：

数据结构：单链表

算法：双指针

注意：代码的鲁棒性

牛客网在线编程专题《剑指offer-面试题15》链表中倒数第k个节点

已经AC的代码：

public class findKthNode {
	
	class ListNode{
		int val;
		ListNode next = null;
		
		public ListNode(int data) {
			this.val = data;
		}
	}
	
	public ListNode head;
	
	public void createLinkedList(int data) {
		if(head == null) {
			head = new ListNode(data);
		}else {
			ListNode node = new ListNode(data);
			node.next = head;
			head = node;
		}
	}
    
    public ListNode FindKthToTail(ListNode head,int k) {
    	if(head == null || k == 0) {
    		return null;
    	}
    	ListNode p1 = head;
    	ListNode p2 = null;
    	for(int i=0; i<k-1; i++) {
    		if(p1.next != null) {
    			p1 = p1.next;
    		}else {
    			return null;
    		}
    	}
    	p2 = head;
    	while(p1.next!=null) {
    		p1 = p1.next;
    		p2 = p2.next;
    	}
    	return p2;
    }

	public static void main(String[] args) {
		findKthNode list = new findKthNode();
		for(int i=0; i<10; i++) {
			list.createLinkedList(i);
		}
		System.out.println(list.FindKthToTail(list.head, 10).val);
	}

}

牛客网在线编程专题《剑指offer-面试题15》链表中倒数第k个节点

相关推荐