链表中倒数第k个结点

1. 题目描述

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

2. 思路

• 遍历存储到数组中，然后取第len-k个
• 遍历一遍获取总长度，倒数第k个等价于正数第len-k个
• 快慢指针，快指针先走k步，然后快慢指针同时走，直到快指针为nil

3. 实现

3.1. 数组

• java

public class 链表中倒数第k个结点
{
    public ListNode FindKthToTail(ListNode head, int k)
    {
        //检查参数
        if (head == null || k <= 0)
        {
            return null;
        }

        //把所有节点放入list中
        LinkedList<ListNode> list = new LinkedList<>();
        ListNode current = head;
        while (current != null)
        {
            list.add(current);
            current = current.next;
        }

        //判断长度
        if (list.size() < k)
        {
            return null;
        }

        //4->5->6，倒数第2个相当于list.size-2
        return list.get(list.size() - k);
    }
}

• go

// 遍历存储到数组中，然后取第len-k个
// 时间：O(n)
// 空间：O(n)
func FindKthToTail(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	vals := make([]*ListNode, 0)
	node := pListHead
	for node != nil {
		vals = append(vals, node)
		node = node.Next
	}

	if len(vals) < k {
		return nil
	}

	return vals[len(vals) - k]
}

3.2. 倒数转正数

//遍历一遍获取总长度，倒数第k个等价于正数第len-k个
// 时间：O(n)
// 空间：O(1)
func FindKthToTail2(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	count := 0
	n := pListHead
	for n != nil {
		count++
		n = n.Next
	}

	if count<k {
		return nil
	}

	n = pListHead
	for i := 0; i < count-k; i++ {
		n = n.Next
	}

	return n
}

3.3. 双指针

• java

 public ListNode FindKthToTail(ListNode head, int k)
    {
        //检查参数
        if (head == null || k <= 0)
        {
            return null;
        }

        //4->5->6->7->8，求倒数第二个
        //         P1 P2
        
        //用两个指针，第一个先走k-1步，注意长度是否足够
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++)
        {
            if (fast == null)
            {
                return null;
            }
            fast = fast.next;

        }
        //两个一起走，第一个走到尾节点时返回第二个指针即可
        while (fast != null)
        {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

• go

//快慢指针，快指针先走k步，然后快慢指针同时走，直到快指针为nil
// 时间：O(n)
// 空间：O(1)
func FindKthToTail3(pListHead *ListNode, k int) *ListNode {
	if pListHead == nil || k <= 0 {
		return nil
	}

	fast := pListHead
	slow := pListHead
	for i := 0; i < k; i++ {
		if fast == nil {
			return nil
		}
		fast = fast.Next
	}

	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}

4. 参考

• 链表中倒数第k个结点_牛客网
• 面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）