剑指Offer-14:输入一个链表，输出该链表中倒数第k个结点。

题目描述：

输入一个链表，输出该链表中倒数第k个结点。例如有一个链表有六个节点1，2，3，4，5，6.则它的倒数第二个节点为5

节点定义如下：

public class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

}

思路一：

设置一个快指针，一个慢指针。像一把尺子，当尺子的一端移动到链表的末尾，则另一端则为倒数第k个节点。

public class Solution {

    public ListNode FindKthToTail(ListNode head,int k) {

       if(head==null||k<=0)

           return null;

        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;

    }

}

思路二：

两次遍历。第一次遍历出链表的长度n,第二次遍历获取链表第n-k+1个节点。

public class Solution {

    public ListNode FindKthToTail(ListNode head,int k) {

       if(head==null||k<=0)

           return null;

        //1.遍历链表的长度

        int n=0;

        ListNode tempNode = head;

        while(tempNode!=null){

            n++;

            tempNode = tempNode.next;

        }

        if(k>n)

            return null;

        //2.遍历获取第n-k+1个节点

        for(int i=0;i<n-k;i++){

            head = head.next;

        }

        return head;

    }

}

思路三：

借助栈来存储所有节点，在利用出栈获取倒数第k个节点

public class Solution {

    public ListNode FindKthToTail(ListNode head,int k) {

       if(head==null||k<=0)

           return null;

        //1.借助栈来存储节点

        Stack<ListNode> stack = new Stack<>();

        while(head!=null){

            stack.push(head);

            head=head.next;

        }

        //判断k是否越界

        if(k>stack.size())

            return null;

        //2.出栈来获取倒数第k个节点

        while(k>1){

            stack.pop();

            k--;

        }

        return stack.pop();

    }

}

巴特西

剑指Offer-14:输入一个链表，输出该链表中倒数第k个结点。

题目描述：

最新文章

热门文章