14 图解剑指Offer 链表中倒数第k个节点 Java题解

た入场券 2023-02-20 12:19 17阅读 0赞

### 14 图解剑指Offer 链表中倒数第k个节点 Java题解 ###

*  14 图解剑指Offer 链表中倒数第k个节点 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 14 图解剑指Offer 链表中倒数第k个节点 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

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

### 题解: ###

//方法一:  
1.首先要判断头节点是否为null，如果为null，直接返回null。  
2.在遍历节点算出链表长度len，判断k是否大于len，如果大于len或k = 0返回null  
3. 设定两个指针 pre after ，pre 先走到k节点  
4.while循环 当 pre.next != null 时 , pre = pre.next after = after.next;  
5.返回 after 即为倒数第k个节点  
//方法二:  
1.首先要判断头节点是否为null，如果为null，直接返回null。  
2.在遍历节点算出链表长度len，判断k是否大于len，如果大于len或k = 0返回null  
3. 设定一个指针 pre  
4.for循环 pre走 len - k 步即可到达倒数第k个节点。  
5.返回 prev

### 图解: ###

方法一:两个指针  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]  
方法二: 一个指针  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 1]

### 代码: ###

/* 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) return null;
            ListNode tempHead = head;
            int len = 0;
            while(tempHead != null) { 
                tempHead = tempHead.next;
                len++;
            }
            if(k > len || k == 0) { 
                return null;
            }
            
            ListNode prev = head;
            ListNode after = head;
            for(int i = 1; i < k; i++) { 
                prev = prev.next;
            }
            while(prev.next != null) { 
                prev = prev.next;
                after = after.next;
            }
            
            return after;
        }
    }
    
    //方法二 
    public class Solution { 
        public ListNode FindKthToTail(ListNode head,int k) { 
            if(head == null) return null;
            
            ListNode dummyHead = head;
            int len = 0;
            
            while(dummyHead != null){ 
                len++;
                dummyHead = dummyHead.next;
            }
            
            if(k==0 || k > len) { 
                return null;
            }
            
            ListNode pre = head;
            for(int i = 0; i < len - k; i++) { 
                pre = pre.next;
            }
            return pre;
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1)  
最坏时间复杂度: 遍历时间复杂度O( n)

[Link 1]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062622165920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627013957441.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70