14_FindKthFromTail

題目描述

輸入一個連結清單，輸出該連結清單中倒數第k個結點。

package com.hwx.swordToOffer._14_FindKthFromTail;

/*
 * 題目描述:
	輸入一個連結清單，輸出該連結清單中倒數第k個結點
 */
public class Solution {

	public static void main(String[] args) {

	}

	/*
	 * {1,2,3,4,5}
	 * 大神的方法：
	 * 定義兩個結點都指向頭節點，先讓第一個p移動k個，然後p和pre一起移動。
	 * 到最後時，p指向空節點(重要！！！邊界問題，p指向空)，pre指向倒數第k個
	 */
	public ListNode FindKthToTail(ListNode head, int k) {
		ListNode p = head;
		ListNode pre = head;
		int i = 0;
		for (; p != null; i++) {
			if (i >= k) {//此時p已經先移動了k步，這時兩個一起走
				pre = pre.next;
			}
			p = p.next;//p總是要走的，并且最後指向null
		}
		return i < k ? null : pre;//i的值為節點的數目。如果k大于節點數目傳回空；否則傳回pre
	}

	/*{1,2,3,4,5}
	 * 我的方法：簡單易懂，但是不好，需要循環兩次，時間複雜度為2*O(logN)。方法1的時間複雜度為O(logN)
	 * 先計算出節點的個數count，倒數第k個節點即正數第count+1-k個節點，cur需要再移動count-k次即為所求節點
	 * 
	 */
	public ListNode FindKthToTail2(ListNode head, int k) {
		int count = 0;
		if (head == null) {
			return null;
		}
		ListNode cur = head;
		while (cur != null) {
			count++;
			cur = cur.next;
		}
		if (k > count) {
			return null;
		}
		for (int i = 0; i < count - k; i++) {
			head = head.next;
		}
		return head;
	}
}

class ListNode {
	int val;
	ListNode next = null;

	ListNode(int val) {
		this.val = val;
	}
}