剑指offer—链表倒数第k个节点 解答

剑指offer—链表倒数第k个节点

题目描述

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

思路

单向链表只能从前往后获取,而无法从后往前获取

  • 方法1:首先我们可以想到的就是遍历一次链表存储链表长度l,然后再进行一次l-k的循环,获得第k个节点

但是该方法耗费时间太多,时间复杂度大,我们想想有没有一种方法只需要遍历一次就可以获得结果

  • 方法2:我们使用两个指针,第一个指针在循环前k次指向后面一个节点,此时第一个指针指向第k个节点,此时开始两个指针移动,直到第一个指针移动到链表末尾,这个时候第二个指针指向的节点就是倒数第k个节点

这种方法就是使用一点点空间换取了大量的时间,使用一个辅助节点来判断第二个节点需要移动到的位置

代码

  • 基础版本
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null||k == 0){
            return null;
        }
        ListNode node = head;
        ListNode kThFlag = head;
        while(kThFlag.next!=null){
            if(k-1>0){
                k--;
                kThFlag = kThFlag.next;
            }else{
                kThFlag = kThFlag.next;
                node = node.next;
            }
        }
        if(k>=2){
            return null;
        }
        return node;
    }
}

看起来很复杂,优化一下,慢慢写出漂亮的代码

  • 简化后
public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null||k == 0)
            return null;
        ListNode q,p;
        q = p = head;
        while(q.next!=null){
            if(--k>0){
                q = q.next;
            }else{
                q = q.next;
                p = p.next;
            }
        }
        return k>=2?null:p;
    }

扩展—删除链表的倒数第N个节点

  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

思路

  • 根据上面一题思路,但是这里要拿到的是删除节点的前一个节点,执行删除node.next=node.next.next
  • 根据这样的思考,既然拿到删除节点的前一个节点,就要考虑删除节点前一个节点是否为null(不存在,删除节点为头结点),想到了使用变量i来存储节点数量(每次循环+1)和m存储倒数节点数n的值
    • 如果i=m说明要删除头结点,我们需要进行单独操作把头结点指向后面一个节点
    • 如果i>m说明删除节点n是有效的,在链表范围内,就执行node.next=node.next.next操作

代码

class Solution {
    //拿到第n-1个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode q,h;
        q = h = head;
        int i = 1;int m = n;
        while(q.next!=null){
            if(n-->0){
                q = q.next;
            }else{
                q = q.next;
                head = head.next;
            }
            i++;
        }
        if(i>m){
            head.next = n>=1||q==head?null:head.next.next;//n>=1用来判断n是否有效(在链表范围内);因为n每次减一,如果循环结束了n还不为0则说明n是无效的数(无法删除该节点)
        }else if(i==m){
            h = h.next;
        }
        return h;
    }
}