转载

【Java 实现经典算法】五:链表中倒数第k个结点

题目来自剑指Offer之十五。

链表结点结构

class ListNode{
    int value;
    ListNode next = null;
    public ListNode(int value){
        this.value = value;
    }
}

基本解法

  • 遍历两次,第一次确定链表长度,第二次返回第n-k+1个结点,即为所求
  • 注意k不能超过链表长度,代码中要进行判断
public static ListNode findKthToTail(ListNode head,int k){
    if(head == null || k <= 0 ){
        return null;
    }
    
    ListNode node = head;
    int nodesNum = 1;
    while(node.next != null){
        nodesNum++;
        node = node.next;
    }
    
    node = head;
    int count = 1;
    while(k <= nodesNum && count != nodesNum - k + 1){
        count++;
        node = node.next;
    }
    if(k <= nodesNum){
        return node;
    }
    return null;
}

高效解法

  • 前后指针,前指针先走k-1个结点,从第k个结点开始,后指针也跟着走
  • 当前指针的next为null时,此时后指针所在的位置就为链表的第k个结点
  • 同样注意还没走到第k个结点链表就结束的情况
public static ListNode findKthToTail2(ListNode head,int k){
    if(head == null || k <= 0)
        return null;
    ListNode pre = head;
    ListNode behind = null;
    for(int i = 0; i < k - 1; i++){
        if(pre.next != null){
            pre = pre.next;
        }else{
            return null;
        }
    }
    
    behind = head;
    while(pre.next != null){
        pre = pre.next;
        behind = behind.next;
    }
    return behind;
}



<p></p>

我组建了一个技术交流群,提供免费的每日科技早报服务,里边也会有众多知名互联网企业的技术大佬一起交流学习,共同成长。需要的朋友可以加我微信(微信ID:919201148),我拉你进群,并有福利相送。

【Java 实现经典算法】五:链表中倒数第k个结点

关注我的微信公众号,回复“礼包”领取我的学习资料

涵盖自学编程、Java技术、分布式笔记、算法刷题和程序员必读电子书等众多资料合集。

【Java 实现经典算法】五:链表中倒数第k个结点

原文  https://segmentfault.com/a/1190000022413789
正文到此结束
Loading...