链表中倒数第k个结点(思路和实现)

KLQ 2020-05-07 09:59:37 java常见问答 5472

下面要给大家分享的实例是和链表中的倒数第k个结点相关的内容,包括了具体的思路和实现方式,一起来了解一下吧。

题目:

输入一个链表,输出这个链表当中倒数第k个结点。

思路1

代码实现:

public ListNode FindKthToTail(ListNode head, int k)
{ //5,{1,2,3,4,5}
    ListNode p, q;
    p = q = head;
    int i = 0;
    for (; p != null; i++)
    {
        if (i >= k)
            q = q.next;
        p = p.next;
    }
    return i < k ? null : q;
}

思路2:

时间复杂度O(n),一次遍历就可以了。

代码实现:

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode pre=null,p=null;
        //两个指针都指向头结点
        p=head;
        pre=head;
        //记录k值
        int a=k;
        //记录节点的个数
        int count=0;
        //p指针先跑,并且记录节点数,当p指针跑了k-1个节点后,pre指针开始跑,
        //当p指针跑到最后时,pre所指指针就是倒数第k个节点
        while(p!=null){
            p=p.next;
            count++;
            if(k
<1){
                pre=pre.next;
            }
            k--;
        }
        //如果节点个数小于所求的倒数第k个节点,则返回空
        if(count
    <a) return null;
        return pre;
            
    }
}

思路3

代码实现:

public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p = head;
        while(k-- != 0){
            if(p == null)
                return null;
            p = p.next;
        }
        while(p != null){
            p = p.next;
            head = head.next;
        }
        return head;
    }

以上就是今天的实例分享了,以上思路和实现仅供参考。

你想了解更多的实例吗?可以继续通过奇Q工具网的java实例栏目来了解呢。

推荐阅读:

java反转链表(思路和实现)

合并两个排序的链表(思路和实现)

从尾到头打印链表java版(栈思路、数组翻转和递归思路)