链表问题心得链表问题心得

链表问题心得

	在链表的问题中当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度
	快一些（比如一次在链表上走两步），或者先让它在链表上走若干步
	——以上引自于《剑指Offer》

1 例子

1.1 链表中倒数第k个节点

题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5

• 分析
  要求遍历一遍链表解决，那么我们可以用两个指针front和late，先让front走k-1步，然后两个指针再一同走，走到结束返回late即可。
• 代码

  class Solution {
  	public ListNode getKthFromEnd(ListNode head, int k) {
  		if (head == null) return null;
  		ListNode front = head, late = head;
  		for (int i = 0; i < k - 1; i++) {
  			if (front.next != null) {
  				front = front.next;
  			} else {
  				return null;
  			}
  		}
  		while (front.next != null) {
  			late = late.next;
  			front = front.next;
  		}
  		return late;
  	}
  }
  

  1.2 leetcode第142题：环形链表II

  思想还是双指针，快慢指针。

最后

以上就是干净天空为你收集整理的链表问题心得链表问题心得的全部内容，希望文章能够帮你解决链表问题心得链表问题心得所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。