寒光博客

[java] 链表实战 倒数第k个节点
倒数第k个节点 求单链表倒数第k个节点思路: 定义p1p2两个节点 然后p2指向正想第k个 接着 p1 p2同时...
扫描右侧二维码阅读全文
13
2019/10

[java] 链表实战 倒数第k个节点

倒数第k个节点

求单链表倒数第k个节点思路:
QQ截图20191013230329.jpg

定义p1p2两个节点
然后p2指向正想第k个
接着 p1 p2同时后移(间距为k)直到p2==null
则此时p1就是倒数第k个节点

如果返回 null 对象则无法get node.value 这个值

代码

package _09_Linear;

public class BottomKthNode {
    static class Node {
        Object value;
        Node next;

        public Node(Object value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "" + value;
        }
    }

    public Node FindKthToTail(Node head, int k) {
        if (head == null || k <= 0) {
            return head;//如果返回 null 对象则无法get node.value 这个值
        }
        Node p1 = head;
        Node p2 = head;
        int count = 0;
        while (p2 != null && count < k) {
            p2 = p2.next;
            count++;
        }
        if (count < k) {
            return head;//如果返回 null 对象则无法get node.value 这个值
        }
        while (p2 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        return p1;

    }

    public static void main(String[] args) {
        int arr[] = {9, 8, 7, 2, 8, 4, 2, 4, 2};
        Node head = new Node(null);//头指针一定为空
        Node p = head;
        for (int i = 0; i < arr.length; i++) {
            p.next = new Node(arr[i]);
            p = p.next;
        }
        //Test
        Node ans = new BottomKthNode().FindKthToTail(head, 9);
        System.out.println(ans.toString());
        ans = new BottomKthNode().FindKthToTail(head, 1);
        System.out.println(ans.toString());
        ans = new BottomKthNode().FindKthToTail(head, 7);
        System.out.println(ans.toString());
    }

}
本文作者:Author:     文章标题:[java] 链表实战 倒数第k个节点
本文地址:https://dxoca.cn/java/292.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 13th, 2019 at 11:06 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment