首页 » Java » 剑指offer面试题15 链表中倒数第k个结点

剑指offer面试题15 链表中倒数第k个结点

原文 http://blog.csdn.net/u013398759/article/details/77369221

2017-08-18 16:20:30阅读(418)

解题思路:

思路1:求链表中倒数第k个节点,也就是正数第n-k+1个结点(假设从1开始计数),此时最直观的做法就是从头开始遍历链表定位到这个第n-k+1个结点即可。但是这种做法需要遍历链表2次,第1次遍历需要求得链表中结点总数,第2次从表头开始找第n-k+1个结点。因此不是最佳解法。

思路2:比较好的做法就是利用双指针,只需遍历链表1次。可以这样考虑,让两个指针p1和p2一开始都指向链表表头,接着让指针p1比p2多走k-1步。然后,p1和p2同时移动,当p1移动至链表末尾时,p2此时正好指向倒数第k个结点处。还需注意一种特殊情况,当k大于链表长度时,即在链表中不存在倒数第k个结点,此时需要单独判断。

public class Solution {
	/**
	 * 常规思路:链表中倒数第k个节点,也就数正数第n-k+1个节点(从1开始计数)
	 * 此时直接从头开始遍历链表定位到这个节点即可,但是这种做法需要遍历节点2次 第1次遍历确定节链表的长度,第2次遍历找到对应节点 
	 * @param head
	 * @param k
	 * @return
	 */
	public ListNode FindKthToTail_simple_idea(ListNode head, int k) {
		// 链表不存在或者k不在合理的范围
		if (head == null || k <= 0) {
			return null;
		}
		// 从头到尾遍历链表,统计链表中节点个数
		int n = 0;
		ListNode p = head;
		while (p != null) {
			n++;
			p = p.next;
		}
		// 此时倒数第k个元素即为正数第n-k+1个
		int target = n - k + 1;
		int index = 1;
		p = head;
		while (index != n - k + 1) {
			index++;
			p = p.next;
		}
		return p;
	}
	class ListNode {
		public int val;
		public ListNode next = null;
		public ListNode(int val) {
			this.val = val;
		}
	}
	/**
	 * 只遍历1次的解法是设置两个指针,因此这道题是一个双指针问题
	 * 先让指针p1比p2多走k-1步,然后两个指针一起走,当指针p1到达链表尾部时,指针p2正好指向 倒数第k-1个
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
	public ListNode FindKthToTail(ListNode head, int k) {
		if (head == null || k <= 0) {
			return null;
		}
		ListNode p1 = head;
		ListNode p2 = head;
		// 首先让p1走k-1步
		// 这里有种特殊情况,如果k大于链表的长度,则p1最终会指向null
		int n = 1;
		while (n != k && p1 != null) {
			n++;
			p1 = p1.next;
		}
		if (p1 != null) {
			//在p1还在链表中的时候
			// 此时p1和p2以同时后移,直到p1到链表的尾节点,
			// 这里有一种特殊情况,若k大于
			while (p1.next != null) {
				p1 = p1.next;
				p2 = p2.next;
			}
			return p2;
		} else {
			return null;
		}
	}
}


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹