首页 » Java » 链表中倒数第k个结点

链表中倒数第k个结点

2016-04-23 13:10:02阅读(390)

链表中倒数第k个结点,有需要的朋友可以参考一下。

题目描述

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

思路:
弄两个指针让他们相距k,当后面的指针跑到链表尾,这时前面一个指针的位置就是要找的节点。注意,边界条件。

package cn.yzx.nowcoder;

/**
 * 题目描述
 * 输入一个链表,输出该链表中倒数第k个结点。
 * @author Administrator
 *
 */
public class FindKthToTail {

    public static void main(String[] args) {
        ListNode head = new ListNode(-1);
        ListNode testList = new ListNode(1);
        ListNode testList1 = new ListNode(2);
        ListNode testList2 = new ListNode(3);
        ListNode testList3 = new ListNode(4);
        ListNode testList4 = new ListNode(5);
        head.next = testList;
        testList.next = testList1;
        testList1.next = testList2;
        testList2.next = testList3;
        testList3.next = testList4;

        ListNode resNode = new FindKthToTail().FindKthToTail(head, 0);
        System.out.println(resNode.val);
    }

    public static class ListNode {
        int val;
        ListNode next = null;

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

    //用两个指针让其相距k
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null)
            return null;
        else if(k==0){
            return null;
        }
        else{
            ListNode endNode = head;
            ListNode resNode = head;
            int flag = 1;
            //让endNode和resNode相距k
            while(endNode.next != null){
                if(flag >= k){
                    resNode = resNode.next;
                }
                endNode = endNode.next;
                flag++;
            }
            if(flag < k){
                return null;
            }
            return resNode;
        }
    }
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹