[数据结构与算法] Java链表中倒数第k个节点、删除链表中倒数第N个节点(快慢指针)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java链表中倒数第k个节点、删除链表中倒数第N个节点(快慢指针) -> 正文阅读

[数据结构与算法]Java链表中倒数第k个节点、删除链表中倒数第N个节点(快慢指针)

剑指offer 19.删除链表中倒数第N个节点

解题思路1:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        if(fast == null){
            return head.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

解题思路2

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp = new ListNode(0, head);
        int len = 0;
        while(tmp.next != null){
            len++;
            tmp = tmp.next;
        }
        ListNode node = new ListNode(0, head);
        int count = 1;
        while(true){
            if(n == len){
                node.next = head.next;
                break;
            }else if(count == len - n){
                head.next = head.next.next;
                break;
            }
            head = head.next;
            count++;
        }
        return node.next;
    }
}

剑指offer 22.链表中倒数第k个节点

解题思路1
快慢指针
让快指针先走k步, 当fast != null时, slow指针刚好指向链表中倒数第k个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head, slow = head;
        for(int i = 1; i <= k; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

解题思路2:
遍历链表, 统计链表的长度count
链表中倒数第k个节点 = 从头开始遍历count - k + 1个节点处

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null && head.next == null){
            return head;
        }
        int count = 0;
        ListNode p = head;
        while(p.next != null){
            count++;
            p = p.next;
        }
        for(int i = 1; i <= count - k + 1; i++){
            head = head.next;
        }
        return head;
    }
}