链表问题——在单链表和双链表中删除倒数第K个节点

客官°小女子只卖身不卖艺 2022-06-08 11:44 137阅读 0赞

【题目】  
　　分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。

【要求】  
　　如果链表长度为N，时间复杂度达到O(N)，时间复杂度达到O(N)，额外空间复杂度达到O(1)

【解答】  
　　本题较为简单，实现方式也是多种多样的，这里只介绍一种方法。  
　　先来看看单链表如何调整。如果链表为空或者K值小于1，这种情况下，参数是无效的，直接返回即可。除此之外，让链表从头开始走到尾，每移动一步，就让k的值减1。  
　　链表：1->2->3，K=4，链表根本不存在倒数第4个节点。  
　　走到的节点：1->2->3  
　　K变化为：3 2 1  
　　  
　　链表：1->2->3，K=3，链表倒数第3个节点是1节点  
　　走到的节点：1->2->3  
　　K变化为：2 1 0  
　　  
　　链表：1->2->3，K=2，链表倒数第2个节点是2节点  
　　走到的节点：1->2->3  
　　K变化为：1 0 -1  
　　  
　　由以上三种情况可知，让链表从头开始走到尾，每移动一步，就让K值减1，当链表走到结尾时，如果K值大于0，说明不用调整链表，因为链表根本没有倒数第K个节点，此时将原链表直接返回即可；如果K值等于0，说明链表倒数第K个节点就是头结点，此时直接返回head.next，也就是原链表的第二个节点，让第二个节点作为链表的头返回即可，相当于删除头节点；接下来，说明一下如果K值小于0，该如何处理。  
　　先明确一点，如果要删除链表的头结点之后的某个节点，实际上需要找到要删除节点的前一个节点，比如：1->2->3，如果想删除节点2，则需要找到节点1，然后把节点1连到节点3上(1->3)，以此来打到删除节点2的目的。  
　　如果K值小于0，如何找到要删除节点的前一个节点呢？方法如下：  
　　1.重新从头节点开始走，每移动一步，就让K的值加1。  
　　2.当K等于0是，移动停止，移动到的节点就是要删除节点的前一个节点。

【代码实现】

public class Node{
        public int value;
        public Node next;
    
        public Node(int data){
            this.value = data;
        }
    }
    
    public Node removeLastKthNode(Node head,int lastKth){
        if(head == null || lastKth < 1){
            return head;
        }
        Node cur = head;
        while(cur != null){
            lastKth--;
            cur = cur.next;
        }
        if(lastKth==0){
            head = head.next;
        }
        if(lastKth<0){
            cur = head;
            while(++lastKth!=0){
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

双链表的调整和单链表的处理几乎一样，只需要注意双链表的删除和单链表的删除不一样就好了

【代码实现】

public class DoubleNode{
        public int value;
        public DoubleNode last;
        public DoubleNode next;
    
        public DoubleNode(int data){
            this.value = data;
        }
    }
    
    public DoubleNode removeLastKthNode(DoubleNode head,int lastKth){
        if(head==null || lastKth < 1){
            return head;
        }
        DoubleNode cur = head;
        while(cur!=null){
            lastKth--;
            cur = cur.next;
        }
        if(lastKth==0){
            head = head.next;
            head.last = null;
        }
        if(lastKth<0){
            cur = head;
            while(++lastKth!=0){
                cur = cur.next;
            }
            DoubleNode newNext = cur.next.next;
            cur.next = newNext;
            if(newNext!=null){
                newNext.last = cur;
            }
        }
        return head;
    }